算法训练营day22

一、二叉搜索树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //得到p q的最大值，跟root比较
        //max < root 向左遍历 ，max > root 继续比较 min > root 向右遍历; min < root root就是最近公共节点
        if (root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);
        if (root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}

二、二叉搜索树的插入操作

参考链接701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

大前提：该树节点值是不重复的

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
//如果root为空，即当前节点为空，说明这个位置可以插入新节点，于是创建一个值为val的新节点并返回。 或者(在递归当中) 如果 root 是空，则新建树节点作为根节点返回即可
        if (root == null) {
            return new TreeNode(val);  //终止条件
        }
//递归调用
//如果root不为空，需要根据当前节点的值与val的大小关系来确定插入的位置。如果root的值小于val，说明val应该插入到右子树中。相反，如果root的值大于或等于val，说明val应该插入到左子树中。
        if (root.val < val) { 
            root.right = insertIntoBST(root.right, val);
        } else {
            root.left = insertIntoBST(root.left, val);
        }
        //返回结果
        return root;
    }
}

二叉搜索树的平均深度是 log⁡n，最坏情况是由于有序插入数据导致二叉搜索树退化成一条链表，此时深度是 n。因此上述两种解法的平均时间复杂度是 O(log⁡n)，最坏时间复杂度是 O(n)。迭代写法的空间复杂度是 O(1)，递归写法由于递归调用时会使用方法栈，而方法栈的深度就是二叉搜索树的深度，所以最坏空间复杂度是 O(n)。

所以说，二叉搜索树的深度是非常影响查找/插入性能的，所以说并不常用，广泛使用的是平衡搜索树。常见的平衡搜索树有 红黑树，B- 树，B+ 树（还有 ACM/OI 大佬们爱的 treap，splay，SBT）等。比如 Java 里的 TreeMap，TreeSet 和 HashMap 中链表的树化都是用红黑树实现的，又比如 InnoDB 的索引存储就是 B+ 树实现的。感兴趣的同学可以去学习下～学成归来之时，可以问候别人——能不能心里有点 B 树～

三、删除二叉搜索树中的节点

重点：当删除当前节点时，使用哪个节点来替代被删除节点？ 使用左子树的最大节点 或 右子树的最小节点 来替代保持 二叉搜索树的性质

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
//找到相等的值时判断左右子树是否为空，左子树为空返回右子树，右子树为空返回左子树，也适用于都为空的情况(return root.right;)
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
//如果都不为空，则遍历到左子树的最右端(最大值)
            TreeNode t = root.left;
            while (t.right != null) t = t.right;
            t.right = root.right;
            return root.left;
        //如果key不等于当前节点值 key > 向右递归，< 向左递归
        } else if (root.val < key) root.right = deleteNode(root.right, key);
        else root.left = deleteNode(root.left, key);
        //返回值
        return root;
    }
}