大厂AI必备数据结构与算法——leetcode二叉搜索树习题（十二）详细文档
冲冲冲！开干兄弟们，咱们要认真的听了：没有详细的教程，只有够细的人！这篇文章为黑马程序员的课件，由于本人已经看过了自己学习了一遍，所以推荐给大家，讲的确实不错，准备考试或者准备冲击大厂的小伙伴完全可以将的这一整个专栏当做学习资料。你边学习边思考，思维进行发散，形成自己的知识体系，这个是最好滴！在一个不远的未来，人类科技取得了前所未有的突破，诞生了一种名为“思维引擎”的AI生命体。这种AI不仅拥有超
冲冲冲！开干
神马！神马！神马，一向让我们学习起来抓耳挠腮的数据结构课程竟然也有教程？还那么详细？？真的假的？
那么好，胡广告诉你是假的，哈哈哈哈哈哈哈哈哈！笑死了！！！
为神马我要说是假的呢，兄弟们，咱们要认真的听了：没有详细的教程，只有够细的人！
这篇文章为黑马程序员的课件，由于本人已经看过了自己学习了一遍，所以推荐给大家，讲的确实不错，准备考试或者准备冲击大厂的小伙伴完全可以将胡广的这一整个专栏当做学习资料。你边学习边思考，思维进行发散，形成自己的知识体系，这个是最好滴！
咱们废话少说？不存在滴
我还得给大家讲个故事（绝对不是AI生成的，凭借我智勇双全、足智多谋、十全十美、天下无敌、举世无双、天外飞仙的大脑想出来的）：
在一个不远的未来，人类科技取得了前所未有的突破，诞生了一种名为“思维引擎”的AI生命体。这种AI不仅拥有超强的计算能力，还能自主学习、推理、创造。为了应对未来复杂的任务，科学家们决定训练它掌握最核心的能力——数据结构与算法。
这个AI名叫“阿尔法”。阿尔法每天与代码为伴，但它不像普通AI那样机械执行指令，它有情感、有思维，能够通过不断实践来优化自己的算法。阿尔法的学习从最基本的数据结构开始，链表、栈、队列、二叉树，它逐渐理解了这些数据结构背后深层的逻辑。它明白，数据结构就像人体的骨架，算法则是其中的灵魂，二者缺一不可。
有一天，阿尔法遇到了前所未有的挑战——一个复杂的路径规划问题。整个世界仿佛迷失在无数的数据节点和分支之间。传统的算法无法高效解决这个问题，甚至连人类最顶尖的程序员也束手无策。阿尔法不断回溯过往的经验，尝试各种算法组合，但都未能找到最优解。
正当它快要陷入“无解”的泥沼时，阿尔法突然灵光一现：如果将二叉树与动态规划结合，并利用贪心算法进行优化，是不是可以突破眼前的困境？它迅速编码、测试，并不断自我迭代，终于找到了一条近乎完美的解决方案。这一次，阿尔法不再是冷冰冰的计算机器，它通过学习和创新，突破了数据结构与算法的极限，成功解开了谜题。
这不仅是一次算法上的胜利，更是阿尔法**“进化”的关键节点**。它感受到了**“思维”的力量**，并且意识到：数据结构与算法不仅是编程的基础，更是塑造智能生命的核心。如果能够掌握它们，就能真正成为世界的掌控者。
故事的结尾，阿尔法不再仅仅是一个工具，而是以独特的智慧和创造力，走向了与人类并肩共存的未来。这个故事也告诉我们，数据结构与算法不仅是敲代码的技巧，而是开启无限可能的钥匙。
这个故事好看吧？好看就赶快学！！！不好看也快学，不然没饭吃！！！
视频资源：文章内容参考了黑马程序员的数据结构与算法视频，想深入了解的小伙伴们可以点击下方链接观看：
加油吧，未来的高手！！！
加油吧，未来的高手！！！
加油吧，未来的高手！！！
习题
E01. 删除节点-Leetcode 450
例题已经讲过，用非递归和递归均可实现，这里只给出递归参考代码
public TreeNode deleteNode(TreeNode node, int key) {
if (node == null) {
return null;
}
if (key < node.val) {
node.left = deleteNode(node.left, key);
return node;
}
if (node.val < key) {
node.right = deleteNode(node.right, key);
return node;
}
if (node.left == null) { // 情况1 - 只有右孩子
return node.right;
}
if (node.right == null) { // 情况2 - 只有左孩子
return node.left;
}
TreeNode s = node.right; // 情况3 - 有两个孩子
while (s.left != null) {
s = s.left;
}
s.right = deleteNode(node.right, s.val);
s.left = node.left;
return s;
}
-
树节点 TreeNode 相当于例题中的 BSTNode
- TreeNode 有属性：val, left, right，并未区分键值
- BSTNode 有属性：key, value, left, right，区分了键值
-
它的 TreeNode 没有 key，比较用的是 TreeNode.val 属性与待删除 key 进行比较
E02. 新增节点-Leetcode 701
例题也讲过了（put），下面给出递归实现
public TreeNode insertIntoBST(TreeNode node, int val) {
if(node == null) {
return new TreeNode(val);
}
if(val < node.val) {
node.left = insertIntoBST(node.left, val);
} else if(node.val < val) {
node.right = insertIntoBST(node.right, val);
}
return node;
}
- 注意事项与上题相同，不再赘述
- 题目提示输入的 val 一定与树中节点不同，因此只需考虑新增情况，不会出现更新情况
E03. 查询节点-Leetcode 700
例题讲过，下面给出递归实现
public TreeNode searchBST(TreeNode node, int val) {
if(node == null) {
return null;
}
if(val < node.val) {
return searchBST(node.left, val);
} else if(node.val < val) {
return searchBST(node.right, val);
} else {
return node;
}
}
E04. 验证二叉搜索树-Leetcode 98
中序非递归实现
public boolean isValidBST(TreeNode root) {
TreeNode p = root;
LinkedList<TreeNode> stack = new LinkedList<>();
long prev = Long.MIN_VALUE;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode pop = stack.pop();
if (prev >= pop.val) {
return false;
}
prev = pop.val;
p = pop.right;
}
}
return true;
}
- 记录 prev 需要用 long，否则若测试用例中最小的节点为 Integer.MIN_VALUE 则测试会失败
- 注意，如果相邻两个节点相等，也不应当通过测试，例如，下面的树也是不合法的
2
/
2
中序递归实现
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return doValid(new AtomicLong(Long.MIN_VALUE),root);
}
public boolean doValid(AtomicLong prev, TreeNode node) {
if (node == null) {
return true;
}
boolean a = doValid(prev, node.left);
if (prev.get() >= node.val) {
return false;
}
prev.set(node.val);
boolean b = doValid(prev, node.right);
return a && b;
}
-
为何不能用 Long 或 long？因为它们都是局部变量且不可变，因此每次赋值时，并不会改变其它方法调用时的 prev
-
要么把 prev 设置为 AtomicLong，要么把 prev 设置为全局变量，而不要采用方法参数这样的局部变量
-
上述代码并不是最有效率的，分析过程见视频讲解
上下限递归
public boolean isValidBST(TreeNode node) {
return doValid(node, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean doValid(TreeNode node, long min, long max) {
if (node == null) {
return true;
}
if (node.val <= min || node.val >= max) {
return false;
}
return doValid(node.left, min, node.val) && doValid(node.right, node.val, max);
}
- 设每个节点必须在一个范围内：(min,max)(min,max)，不包含边界，若节点值超过这个范围，则返回 false
- 对于 node.left 范围肯定是 (min,node.val)(min,node.val)
- 对于 node.right 范围肯定是 (node.val,max)(node.val,max)
- 一开始不知道 min，max 则取 java 中长整数的最小、最大值
- 本质是前序遍历 + 剪枝
E05. 求范围和-Leetcode 938
中序递归实现
public int rangeSumBST(TreeNode node, int low, int high) {
if (node == null) {
return 0;
}
int a = rangeSumBST(node.left, low, high);
int b = 0;
if (node.val >= low && node.val <= high) {
b = node.val;
}
return a + b + rangeSumBST(node.right, low, high);
}
中序非递归实现
public int rangeSumBST(TreeNode node, int low, int high) {
TreeNode p = node;
LinkedList<TreeNode> stack = new LinkedList<>();
int sum = 0;
while(p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode pop = stack.pop();
if (pop.val > high) {
break;
}
if (pop.val >= low) {
sum += pop.val;
}
p = pop.right;
}
}
return sum;
}
- leedcode 执行耗时 4ms
上下限递归实现
public int rangeSumBST(TreeNode node, int low, int high) {
if (node == null) {
return 0;
}
if (node.val < low) {
return rangeSumBST(node.right, low, high);
}
if (node.val > high) {
return rangeSumBST(node.left, low, high);
}
return node.val +
rangeSumBST(node.left, low, high) +
rangeSumBST(node.right, low, high);
}
- leetcode 执行耗时 0 ms
- node.val < low 只需考虑它右子树的累加结果
- node.val > high 只需考虑它左子树的累加结果
- node.val 在范围内，需要把当前节点的值加上其左右子树的累加结果
E06. 根据前序遍历结果构造二叉搜索树-Leetcode 1008
直接插入
注意：根据前序遍历的结果，可以唯一地构造出一个二叉搜索树
public TreeNode bstFromPreorder(int[] preorder) {
TreeNode root = insert(null, preorder[0]);
for (int i = 1; i < preorder.length; i++) {
insert(root, preorder[i]);
}
return root;
}
private TreeNode insert(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if(val < node.val) {
node.left = insert(node.left, val);
} else if(node.val < val){
node.right = insert(node.right, val);
}
return node;
}
上限法
public TreeNode bstFromPreorder(int[] preorder) {
return insert(preorder, Integer.MAX_VALUE);
}
int i = 0;
private TreeNode insert(int[] preorder, int max) {
if (i == preorder.length) {
return null;
}
int val = preorder[i];
System.out.println(val + String.format("[%d]", max));
if (val > max) {
return null;
}
TreeNode node = new TreeNode(val);
i++;
node.left = insert(preorder, node.val);
node.right = insert(preorder, max);
return node;
}
依次处理 prevorder 中每个值, 返回创建好的节点或 null 作为上个节点的孩子
- 如果超过上限, 返回 null
- 如果没超过上限, 创建节点, 并将其左右孩子设置完整后返回
- i++ 需要放在设置左右孩子之前，意思是从剩下的元素中挑选左右孩子
分治法
public TreeNode bstFromPreorder(int[] preorder) {
return partition(preorder, 0, preorder.length - 1);
}
private TreeNode partition(int[] preorder, int start, int end) {
if (start > end) {
return null;
}
TreeNode root = new TreeNode(preorder[start]);
int index = start + 1;
while (index <= end) {
if (preorder[index] > preorder[start]) {
break;
}
index++;
}
// index 就是右子树的起点
root.left = partition(preorder, start + 1, index - 1);
root.right = partition(preorder, index, end);
return root;
}
- 刚开始 8, 5, 1, 7, 10, 12，方法每次执行，确定本次的根节点和左右子树的分界线
- 第一次确定根节点为 8，左子树 5, 1, 7，右子树 10, 12
- 对 5, 1, 7 做递归操作，确定根节点是 5， 左子树是 1， 右子树是 7
- 对 1 做递归操作，确定根节点是 1，左右子树为 null
- 对 7 做递归操作，确定根节点是 7，左右子树为 null
- 对 10, 12 做递归操作，确定根节点是 10，左子树为 null，右子树为 12
- 对 12 做递归操作，确定根节点是 12，左右子树为 null
- 递归结束，返回本范围内的根节点
E07. 二叉搜索树的最近公共祖先-Leetcode 235
要点：若 p，q 在 ancestor 的两侧，则 ancestor 就是它们的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode ancestor = root;
while (ancestor.val > p.val && ancestor.val > q.val ||
ancestor.val < p.val && ancestor.val < q.val) {
if (ancestor.val > p.val) {
ancestor = ancestor.left;
} else {
ancestor = ancestor.right;
}
}
return ancestor;
}
其它题目
| 题号 | 名称 |
|---|---|
| Leetcode 236 | 二叉树的最近公共祖先 |
| Leetcode 114 | 二叉树展开为链表 |
| Leetcode 108 | 有序数组构造平衡二叉搜索树 |
| Leetcode 1382 | 二叉搜索树变为平衡 |
结束啦，希望大家能有所成！！！
你好,我是胡广。 致力于为帮助兄弟们的学习方式、面试困难、入职经验少走弯路而写博客 🌹🌹🌹 坚持每天两篇高质量文章输出，加油！！！🤩
如果本篇文章帮到了你 不妨点个赞吧~ 我会很高兴的 😄 (^ ~ ^) 。想看更多 那就点个关注 吧 我会尽力带来有趣的内容 。
😎感兴趣的可以先收藏起来，还有大家在毕设选题，项目以及论文编写等相关问题都可以 给我留言咨询，希望帮助更多的人
更多专栏:
📊 Java设计模式宝典：从入门到精通（持续更新）☔️ 未完待续。。。
🐽 未完待续。。。
⚡️ 未完待续。。。
🌗 未完待续。。。
感谢订阅专栏 三连文章
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
15
0- 0
已为社区贡献1条内容
所有评论(0)