算法训练营day22

发布于:2024-04-25 ⋅ 阅读:(37) ⋅ 点赞:(0)
一、二叉搜索树的最近公共祖先
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;
    }
}

网站公告

今日签到

点亮在社区的每一天
去签到