算法训练营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;
    }
}