个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天又到了我们的每日刷题环节今天的主要内容是二叉搜索树的最近公共祖先问题其实这几天主要讲的就是二叉搜索树的算法内容让我们一起来看看吧。摘要本文讲解了二叉搜索树和普通二叉树中寻找最近公共祖先LCA的算法。对于普通二叉树采用递归回溯方法通过判断左右子树返回值确定LCA对于二叉搜索树利用其有序特性通过比较节点值大小直接定位LCA无需遍历整棵树。文章通过具体示例和代码实现对比了两种方法的差异指出二叉搜索树的解法更简洁高效。最后提供了两种方式的代码实现并鼓励读者点赞支持。知识铺垫二叉树的最近公共祖先Lowest Common Ancestor, LCA定义对于二叉树中的两个节点 p 和 q它们的最近公共祖先是指一个节点可以是 p 或 q 本身同时满足该节点是 p 和 q 的祖先即 p 和 q 都在它的子树中或者它本身等于 p 或 q。它是所有祖先中深度最大离 p 和 q 最近的那个。通俗解释把二叉树想象成一个家谱树。公共祖先p 和 q 往上走都能碰到的节点。最近离 p 和 q 最近的那个公共祖先也就是深度最大的那个。例如3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4节点 5 和 1 的最近公共祖先 3节点 5 和 4 的最近公共祖先 5因为 5 本身就是祖先节点 7 和 4 的最近公共祖先 2核心性质关键点一个节点可以是它自己的祖先当它等于 p 或 q 时。如果 p 和 q 一个在左子树一个在右子树那么当前根节点就是它们的最近公共祖先。如果 p 和 q 都在左子树或都在右子树那么 LCA 在左子树或右子树中。普通二叉树的处理题目背景236.二叉树的最近公共祖先给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1输出3解释节点 5 和节点 1 的最近公共祖先是节点 3 。例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4输出5解释节点 5 和节点 4 的最近公共祖先是节点 5 。 因为根据定义最近公共祖先节点可以为节点本身。示例 3输入root [1,2], p 1, q 2输出1提示树中节点数目在范围[2, 105]内。-109 Node.val 109所有Node.val互不相同。p ! qp和q均存在于给定的二叉树中。题目解析既然是普通的二叉树对于查找二叉树的最近公共祖先肯定是有一种普遍的处理方式。分析完题目我们发现这道题的关键是从下往上思考而不是从上往下找路径。所以这里我们用最基础的递归回溯的方法进行实现。首先写递归那么就要知道递归的三要素以及递归要达成的目的递归的目的是要知道在当前以 root 为根的子树中找到并返回 p 和 q 的“最佳候选”节点。三要素①递归的终止条件递推关系LCA(root) 根据 LCA(root.left) 和 LCA(root.right) 的结果决定root null含义走到了树的底部,越过了叶子节点。目的表示这条路径上不可能找到 p 或 q。返回null。root p含义当前节点就是要找的 p。目的立刻停止向下搜索(因为 p 已经找到,而且题目保证 p 和 q 一定存在,再往下找纯属浪费)。返回p节点本身(告诉上层“我在这里”)。root q含义当前节点就是要找的 q。目的同上,立刻停止。返回q节点本身。为什么找到 p 或 q 就停是正确的你可能会想万一 p 是 q 的祖先呢比如 p5, q6。在节点 5 就停下来了,岂不是没往下找到 6这正是关键设计如果 p 是 q 的祖先,那么p本身就是 LCA。递归在p处终止,返回p给上层。上层根据左右结果判断,最终答案就是p。根本不需要找到q,因为 LCA 已经确定。提前终止不会漏掉答案,反而避免了无效搜索。②递归的逻辑1递归查找左子树2 递归查找右子树3 根据左右返回结果判断每个节点只做三件事如果自己是 p 或 q就立即上报自己。否则问左孩子和右孩子分别找到了什么。根据左右上报的结果决定自己是“LCA”还是“传话筒”。其实就是遍历只不过需要从下到上的回溯因为终止条件在下面生效之后得到结果向上传话一次返回到上面之后再具体来判断是不是最近的公共祖先。具体实现1.最近公共祖先是根节点这样的递归得到的左右返回值都不为null就代表目标pq恰好在这个根节点的两侧那这个跟节点自然而然就是最近的公共祖先了。if (left ! null right ! null) { // p 和 q 分别在当前节点的左右子树中 → 当前节点就是 LCA return root;2.只在左边找到那么就代表右子树没有目标值全在左子树这样来看先找到的目标值直接返回提前结束因为就算再找结果仍然是先找的节点后找到的祖先就是先找到的第一个找到的祖先就是他自己。else if (left ! null) { // 只在左边找到 → 返回左边的结果 return left;3.只在右边找到同理左子树没有目标值递归从下到上返回的结果都是null只在右子树有返回值先找到的就是祖先。else { // 只在右边找到或两边都没找到 return right;③递归的返回值返回值含义null在当前子树中既没有找到 p也没有找到 qp或q在当前子树中找到了 p 或 q但还没有找到另一个其他节点如 2、3在当前子树中已经同时找到了 p 和 q这个节点就是它们的 LCA进程与形象理解先明确递归与回溯的关系递从根节点一路往下走走到叶子或找到 p/q。回溯当递归调用返回后从下往上返回到上一层带着返回值找到了什么其实就是弹栈的过程了不是独立的一部分。在回溯过程中每一层都会根据左右子树返回的结果判断自己该返回什么给更上层。关键回溯不是倒着走一遍而是递归函数执行完后的返回过程。具体例子树结构3 / \ 5 1 / \ 6 2 / \ 7 4查找p 7, q 4第 1 步从根节点开始调用lowestCommonAncestor(3, 7, 4)进入函数节点 33 ≠ 7, ≠ 4, ≠ null执行javaleft lowestCommonAncestor(3.left, 7, 4) // 去左子树 5 right lowestCommonAncestor(3.right, 7, 4) // 去右子树 1第 2 步进入左子树节点 5lowestCommonAncestor(5, 7, 4)5 ≠ 7, ≠ 4继续javaleft lowestCommonAncestor(5.left, 7, 4) // 去左孩子 6 right lowestCommonAncestor(5.right, 7, 4) // 去右孩子 2第 3 步进入节点 6lowestCommonAncestor(6, 7, 4)6 ≠ 7, ≠ 4left 递归(6.left) → nullright 递归(6.right) → nullleft 和 right 都 null →返回 null给节点 5这是第一次回溯回溯结果节点 5 的left null第 4 步进入节点 2lowestCommonAncestor(2, 7, 4)2 ≠ 7, ≠ 4继续javaleft lowestCommonAncestor(2.left, 7, 4) // 去 7 right lowestCommonAncestor(2.right, 7, 4) // 去 4第 5 步进入节点 7lowestCommonAncestor(7, 7, 4)7 p→ 触发终止条件直接返回 7不再往下找回溯节点 2 的left 7第 6 步进入节点 4lowestCommonAncestor(4, 7, 4)4 q→ 直接返回 4回溯节点 2 的right 4第 7 步在节点 2 上回溯判断现在回到lowestCommonAncestor(2, 7, 4)的调用点left 7非空right 4非空满足left ! null right ! null→返回 2 给上一级节点 5回溯节点 5 的right 2第 8 步回到节点 5现在lowestCommonAncestor(5, 7, 4)拿到了left null来自节点 6right 2来自节点 2left null, right ! null→返回 right也就是 2 给上一级节点 3回溯节点 3 的left 2第 9 步节点 3 的右子树节点 1lowestCommonAncestor(1, 7, 4)1 不是 p/q递归左右孩子left(0) → nullright(8) → null都 null →返回 null 给节点 3回溯节点 3 的right null第 10 步根节点 3 最终判断left 2right nullleft ! null, right null→返回 2最终结果节点 2✅用传话游戏比喻回溯过程想象你在树的最底层找到了两个人7 和 4然后开始向上传消息节点 7 说“我找到 p 了” → 传给父节点 2节点 4 说“我找到 q 了” → 传给父节点 2节点 2 收到左右两个消息说“那我是 LCA” → 把“我是 2”传给父节点 5节点 5 只从右边收到“我是 2”左边没消息于是继续向上传“我是 2”节点 3 从左边收到“我是 2”右边没消息于是最后返回 2回溯就是从收到消息的节点把结果往上传的过程。题目答案/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(rootnull||rootp||rootq){ return root; } TreeNode leftlowestCommonAncestor(root.left,p,q); TreeNode rightlowestCommonAncestor(root.right,p,q); if(left!nullright!null){ return root; }else if(left!null){ return left; }else{ return right; } } }我们学习完了普通二叉树的最近公共祖先来看看二叉搜索树的最近公共祖先吧题目背景235.二叉搜索树 的最近公共祖先。给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”例如给定如下二叉搜索树: root [6,2,8,0,4,7,9,null,null,3,5]示例 1:输入:root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 8输出:6解释:节点2和节点8的最近公共祖先是6。示例 2:输入:root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 4输出:2解释:节点2和节点4的最近公共祖先是2, 因为根据定义最近公共祖先节点可以为节点本身。说明:所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉搜索树中。题目分析对比一下我们上面所说的普通二叉树二叉搜索树是有顺序的这个特性给我们带来了很大的遍历首先我们不用遍历一整棵树我们只需要先从根节点判断如果 p 和 q都小于当前节点 → 答案在左子树如果 p 和 q都大于当前节点 → 答案在右子树否则一个小于、一个大于或者其中一个等于当前节点→当前节点就是 LCA比普通二叉树的逻辑简单不要太多当不是同一个根节点是我们照旧通过递归遍历左右子树找到第一个目标值直接返回即可。题目答案递归法class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (p.val root.val q.val root.val) { return lowestCommonAncestor(root.left, p, q); } if (p.val root.val q.val root.val) { return lowestCommonAncestor(root.right, p, q); } return root; } }迭代法class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root ! null) { if (p.val root.val q.val root.val) { root root.left; // 都在左子树 } else if (p.val root.val q.val root.val) { root root.right; // 都在右子树 } else { return root; // 分居两侧 或 一个是另一个的祖先 } } return null; } }普通二叉树 vs 二叉搜索树完整对比表维度普通二叉树236二叉搜索树235核心特性无顺序左 根 右是否需要遍历整棵树最坏需要 O(N)不需要最多 O(H)遍历方向后序遍历先左后右再回溯单路下降只走一条路径决策依据左右子树返回值是否都非空p、q 与 root 的值比较能否提前终止找到 p 或 q 就停单分支找到分界点就停空间复杂度O(H) 递归栈O(1) 迭代 / O(H) 递归代码复杂度稍复杂需要理解回溯极简3 个 if结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
