剑指offer-81、⼆叉搜索树的最近公共祖先
<h2 id="题描述">题⽬描述</h2><p>给定⼀个⼆叉搜索树, 找到该树中两个指定节点的最近公共祖先。</p>
<ol>
<li>对于该题的最近的公共祖先定义:对于有根树T的两个结点p 、q ，最近公共祖先LCA(T,p,q)表示⼀个结点x ，满⾜x 是p 和q 的祖先且x 的深度尽可能⼤。在这⾥，⼀个节点也可以是它⾃⼰的祖先.</li>
<li>⼆叉搜索树是若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值； 若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值</li>
<li>所有节点的值都是唯⼀的。</li>
<li>p 、q 为不同节点且均存在于给定的⼆叉搜索树中。</li>
</ol>
<p>如果给定以下搜索⼆叉树: {7,1,12,0,4,11,14,#,#,3,5} ，如下图:</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505182005497.png" alt="" loading="lazy"></p>
<p>示例1<br>
输⼊: {7,1,12,0,4,11,14,#,#,3,5},1,12<br>
输出: 7<br>
说明：节点1 和 节点12的最近公共祖先是7</p>
<p>示例2：<br>
输⼊: {7,1,12,0,4,11,14,#,#,3,5},12,11<br>
输出: 12<br>
说明：因为⼀个节点也可以是它⾃⼰的祖先.所以输出12</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="迭代遍历">迭代遍历</h3>
<p>二叉搜索树（BST）的特性，通过迭代查找公共祖先，根据节点值大小关系，决定向左子树或右子树查找</p>
<pre><code class="language-java">public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
TreeNode current = root;
while (current != null) {
// 如果p和q的值都小于当前节点，LCA在左子树
if (p.val < current.val && q.val < current.val) {
current = current.left;
}
// 如果p和q的值都大于当前节点，LCA在右子树
else if (p.val > current.val && q.val > current.val) {
current = current.right;
}
// 否则当前节点就是LCA
else {
return current;
}
}
return null; // 未找到
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(h)，h为树高，平均O(log n)，最坏O(n)</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数空间</li>
</ul>
<h3 id="递归遍历">递归遍历</h3>
<p>递归判断节点值关系，决定向左或右递归查找</p>
<p>题⽬已经保证了，两个节点 p , q 都在树上，我们取出根节点 7 ，假设⼩于 7 ，则在左⼦树，如果⼤于7 ，则在右⼦树。</p>
<p>需要查找的两个节点，但凡有⼀个等于根节点，它们的⽗节点就是根节点，因为⼀个节点的⽗节点可以是⾃身（题⽬有说明）。</p>
<p>如果⼀个⼤于根节点，⼀个⼩于更节点，其最近公共祖先也是根节点。如果两个都⼤于，或者两个都⼩于，怎么办？</p>
<p>当然是递归，如果两个都⼩于，那么就取当前的左⼦树进⾏递归，直到符合要求。⽐如查找，3 和 5，由于 3 和 5 都⼩于 7，那么取左⼦树 1 下⾯的进⾏递归：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505182007430.png" alt="" loading="lazy"></p>
<pre><code class="language-java">class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution68 {
public int lowestCommonAncestor(TreeNode root, int p, int q) {
TreeNode result = commonAncestor(root, p, q);
return result == null ? -1 : result.val;
}
public TreeNode commonAncestor(TreeNode root, int p, int q) {
// 等于空
if (root == null) {
return null;
}
if (root.val == p || root.val == q) {
// 有⼀个值等于根节点
return root;
}
// 在左⼦树
if (p < root.val && q < root.val) {
return commonAncestor(root.left, p, q);
} else if (p > root.val && q > root.val) {
// 两个都在右⼦树
return commonAncestor(root.right, p, q);
} else {
return root;
}
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(h)，递归深度为树高</li>
<li><strong>空间复杂度</strong>：O(h)，递归调用栈空间</li>
</ul>
<h3 id="通用二叉树">通用二叉树</h3>
<p>假设这道题条件改⼀下，如果不是⼆叉搜索树，怎么办？</p>
<p>如果不是⼆叉搜索树，那么我们不能直接判断出它在左⼦树，还是在右⼦树。不如暴⼒点，先在左⼦树中找，如果右⼦树没找到，说明都在左⼦树，如果左⼦树没找到，说明都在右⼦树，如果两个都分别存在，说明当前节点就是他们的⽗节点。</p>
<pre><code class="language-java">public class Solution68 {
public int lowestCommonAncestor(TreeNode root, int p, int q) {
TreeNode result = commonAncestor(root, p, q);
return result == null ? -1 : result.val;
}
public TreeNode commonAncestor(TreeNode root, int p, int q) {
if (null == root) {
return null;
}
if (root.val == p || root.val == q) {
return root;
}
TreeNode left = commonAncestor(root.left, p, q);
TreeNode right = commonAncestor(root.right, p, q);
if (left == null) {
return right;
} else if (right == null) {
return left;
} else {
return root;
}
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要遍历整个树</li>
<li><strong>空间复杂度</strong>：O(h)，递归栈深度</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19682115
頁:
[1]