判断一棵二叉树是否为搜索二叉树和完全二叉树

判断一棵二叉树是否为搜索二叉树和完全二叉树_牛客题霸_牛客网

问题简述

给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。
输出描述：分别输出是否为搜索二叉树、完全二叉树。

思路

• 判断二叉搜索树的条件：

  • 当前节点的值大于左树的最大值，小于右树的最小值，且左右子树都是二叉搜索树；

• 判断完全二叉树的条件：

  • 左右子树都是满二叉树，且高度相同（满二叉树）；

  • 左右子树都是满二叉树，且左子树的高度+1；

  • 左子树是满二叉树，右子树是完全二叉树，且高度相同；

  • 左子树是完全二叉树，右子树是满二叉树，且左子树的高度+1；

• 综上：

  • 我们需要存储信息有：最大值、最小值、高度、是否二叉搜索树、是否满二叉树、是否完全二叉树；

  • 对空节点，初始化为：无穷小、无穷大、0、是、是、是；

• 详见代码；

Python

class Solution:
    def judgeIt(self , root: TreeNode) -> List[bool]:
        
        from dataclasses import dataclass
        
        @dataclass
        class Info:
            mx: int  # 整棵树的最大值
            mi: int  # 整棵树的最小值
            height: int    # 树的高度
            is_bst: bool   # 是否搜索二叉树
            is_full: bool  # 是否满二叉树
            is_cbt: bool   # 是否完全二叉树
        
        def dfs(x):
            if not x: return Info(float('-inf'), float('inf'), 0, True, True, True)
            
            l, r = dfs(x.left), dfs(x.right)
            # 使用左右子树的信息得到当前节点的信息
            mx = max(x.val, r.mx)
            mi = min(x.val, l.mi)
            height = max(l.height, r.height) + 1
            is_bst = l.is_bst and r.is_bst and l.mx < x.val < r.mi
            is_full = l.is_full and r.is_full and l.height == r.height
            is_cbt = is_full or \
                l.is_full and r.is_full and l.height - 1 == r.height or \
                l.is_full and r.is_cbt and l.height == r.height or \
                l.is_cbt and r.is_full and l.height - 1 == r.height
            
            return Info(mx, mi, height, is_bst, is_full, is_cbt)
            
        info = dfs(root)
        return info.is_bst, info.is_cbt