本文主要是介绍算法训练营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;}
}
二叉搜索树的平均深度是 logn,最坏情况是由于有序插入数据导致二叉搜索树退化成一条链表,此时深度是 n。因此上述两种解法的平均时间复杂度是 O(logn),最坏时间复杂度是 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;}
}
这篇关于算法训练营day22的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!