【40讲系列5】二叉树、二叉搜索树

一、理论

二分搜索树：

　　1. 每个节点的键值大于左孩子；

　　2. 每个节点的键值小于右孩子；

　　3. 以左右孩子为根的子树仍为二分搜索树。

对于二分搜索树，要求掌握插入、查找、删除基本操作，以及

　　查找最大值、最小值；

　　给定一个数据，寻找前驱和后继，以及上界和下界

　　某个元素的排名rank

　　寻找第k大或小元素select

二、典型例题

☆☆①：验证二叉搜索树（LC98）

思路：中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，满足BST，继续遍历；否则返回false。

中序遍历（递归）：

class Solution {
    private TreeNode pre; // 前一个节点, 定义为全局的

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        // 访问左子树
        if(!isValidBST(root.left)){
            return false;
        }
        // 访问当前节点，如果当前节点<=中序遍历的前一个节点，直接返回false
        if (pre != null && pre.val >= root.val){
            return false;
        }
        pre = root;
        // 访问右子树
        return isValidBST(root.right);
    }
}

中序遍历（非递归）：

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null && pre.val >= root.val){
                return false;
            }
            pre = root;
            root = root.right;
        }
        return true;
    }
}

☆☆②：二叉树的最近公共祖先（LC236）

class Solution {
    // 时间复杂度O(n)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (p == root || q == root)  // 其中一个节点就在根节点的位置
            return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left != null && right != null) return root;
        if (left == null) return right;
        if (right == null) return left;
        return null; // left和right都为空（即左右子树都不包含pq）
    }
}

③：二叉搜索树的最新公共祖先（LC235）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归写法
        /*
        if (p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if (p.val > root.val && q.val >root.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root; // 对应三种情况
        */
        // 非递归写法
        while (root != null){
            if (p.val < root.val && q.val < root.val){
                root = root.left;
            }else if (p.val > root.val && q.val > root.val){
                root = root.right;
            }else{
                return root;
            }
        }
        return null;
    }
}

三、扩展例题

第一组：LeetCode104. 二叉树的最大深度、LeetCode111. 二叉树的最小深度

第二组：LeetCode226. 翻转二叉树、LeetCode100. 相同的树、LeetCode101. 对称二叉树、LeetCode222. 完全二叉树的节点个数、LeetCode110. 平衡二叉树

第三组：LeetCode112. 路径总和、LeetCode404. 左叶子之和

第四组：LeetCode257. 二叉树的所有路径、LeetCode113. 路径总和 II、LeetCode129. 求根到叶子节点数字之和、LeetCode222. 完全二叉树的节点个数、LeetCode437. 路径总和 III