验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

直接递归判断

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def helper(root, pre_val, next_val):
            if not root:
                return True
            if root.val >= next_val or root.val <= pre_val:
                return False
            
            return helper(root.left, pre_val, root.val) and helper(root.right, root.val, next_val)
        
        return helper(root, float('-inf'), float('inf'))

中序遍历的思路

中序遍历得到的数组必然是从小到大有序排列的。

递归思路

时间复杂度和空间复杂度均为O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def inOrder(root):
            ans = []
            if not root:
                return ans
            ans += inOrder(root.left)
            ans.append(root.val)
            ans += inOrder(root.right)
            return ans
        
        ans = inOrder(root)
        if not ans:
            return True
        for i in range(1, len(ans)):
            if ans[i-1] >= ans[i]:
                return False
        
        return True

非递归思路

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        
        stack = []
        p = root
        pre_val = float('-inf')
        while stack or p:
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()
            if p.val <= pre_val:
                return False
            pre_val = p.val
            p = p.right
        return True

用C++重写一遍加深记忆，这个时候就体现出Python写代码的方便性了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr){
            return true;
        }
        stack<TreeNode*> s;
        long preval = (long)INT_MIN-1;
        TreeNode* p = root;
        while (p != nullptr || !s.empty()){
            while (p != nullptr){
                s.push(p);
                p = p->left;
            }
            p = s.top();
            s.pop();
            // 后面被访问的数要严格大于前一个数
            // 由于int最小可能为INT_MIN, 所以preval初始化值比INT_MIN小1
            // 或者对于边界值单独处理
            if (p->val <= preval){
                return false;
            }
            preval = p->val;
            p = p->right;
        }
        return true;
    }
};

二叉树的完全性检验

给定一个二叉树的 root ，确定它是否是一个完全二叉树。

在一个完全二叉树中，除了最后一个关卡外，所有关卡都是完全被填满的，
并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2^h 节点之间的最后一级 h 。

层序遍历的思路

如果将完全二叉数用数组存储，那么它的节点序号是顺序的。
如果有n个节点，则最后一个节点的序号应该是n-1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        if not root:
            return True
        
        queue = collections.deque([(root, 0)])
        count = 0
        while queue:
            size = len(queue)
            for i in range(size):
                p, p_index = queue.popleft()
                # 完全二叉树的序号是顺序的
                if count != p_index:
                    return False
                count += 1
                if p.left:
                    queue.append((p.left, p_index*2+1))
                if p.right:
                    queue.append((p.right, p_index*2+2))
        
        return True

汇芳书院

二叉树的合法性判断(系列)