剑指offer-81、⼆叉搜索树的最近公共祖先

题⽬描述

给定⼀个⼆叉搜索树, 找到该树中两个指定节点的最近公共祖先。

• 对于该题的最近的公共祖先定义:对于有根树T的两个结点p 、q ，最近公共祖先LCA(T,p,q)表示⼀个结点x ，满⾜x 是p 和q 的祖先且x 的深度尽可能⼤。在这⾥，⼀个节点也可以是它⾃⼰的祖先.
  
• ⼆叉搜索树是若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值； 若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值
  
• 所有节点的值都是唯⼀的。
  
• p 、q 为不同节点且均存在于给定的⼆叉搜索树中。
  

如果给定以下搜索⼆叉树: {7,1,12,0,4,11,14,#,#,3,5} ，如下图:

示例1
输⼊: {7,1,12,0,4,11,14,#,#,3,5},1,12
输出: 7
说明：节点1 和 节点12的最近公共祖先是7
示例2：
输⼊: {7,1,12,0,4,11,14,#,#,3,5},12,11
输出: 12
说明：因为⼀个节点也可以是它⾃⼰的祖先.所以输出12
思路及解答

迭代遍历

二叉搜索树（BST）的特性，通过迭代查找公共祖先，根据节点值大小关系，决定向左子树或右子树查找

1. public class Solution {
2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
3.         if (root == null) return null;
4.         
5.         TreeNode current = root;
6.         
7.         while (current != null) {
8.             // 如果p和q的值都小于当前节点，LCA在左子树
9.             if (p.val < current.val && q.val < current.val) {
10.                 current = current.left;
11.             }
12.             // 如果p和q的值都大于当前节点，LCA在右子树
13.             else if (p.val > current.val && q.val > current.val) {
14.                 current = current.right;
15.             }
16.             // 否则当前节点就是LCA
17.             else {
18.                 return current;
19.             }
20.         }
21.         
22.         return null; // 未找到
23.     }
24. }

复制代码

• 时间复杂度：O(h)，h为树高，平均O(log n)，最坏O(n)
  
• 空间复杂度：O(1)，只使用常数空间
  

递归遍历

递归判断节点值关系，决定向左或右递归查找
题⽬已经保证了，两个节点 p , q 都在树上，我们取出根节点 7 ，假设⼩于 7 ，则在左⼦树，如果⼤于7 ，则在右⼦树。
需要查找的两个节点，但凡有⼀个等于根节点，它们的⽗节点就是根节点，因为⼀个节点的⽗节点可以是⾃身（题⽬有说明）。
如果⼀个⼤于根节点，⼀个⼩于更节点，其最近公共祖先也是根节点。如果两个都⼤于，或者两个都⼩于，怎么办？
当然是递归，如果两个都⼩于，那么就取当前的左⼦树进⾏递归，直到符合要求。⽐如查找，3 和 5，由于 3 和 5 都⼩于 7，那么取左⼦树 1 下⾯的进⾏递归：

1. class TreeNode {
2.     int val = 0;
3.     TreeNode left = null;
4.     TreeNode right = null;
5.     public TreeNode(int val) {
6.         this.val = val;
7.     }
8. }
9. public class Solution68 {
10.     public int lowestCommonAncestor(TreeNode root, int p, int q) {
11.         TreeNode result = commonAncestor(root, p, q);
12.         return result == null ? -1 : result.val;
13.     }
14.     public TreeNode commonAncestor(TreeNode root, int p, int q) {
15.         // 等于空
16.         if (root == null) {
17.             return null;
18.         }
19.         if (root.val == p || root.val == q) {
20.             // 有⼀个值等于根节点
21.             return root;
22.         }
23.         // 在左⼦树
24.         if (p < root.val && q < root.val) {
25.             return commonAncestor(root.left, p, q);
26.         } else if (p > root.val && q > root.val) {
27.             // 两个都在右⼦树
28.             return commonAncestor(root.right, p, q);
29.         } else {
30.             return root;
31.         }
32.     }
33. }

复制代码

• 时间复杂度：O(h)，递归深度为树高
  
• 空间复杂度：O(h)，递归调用栈空间
  

通用二叉树

假设这道题条件改⼀下，如果不是⼆叉搜索树，怎么办？
如果不是⼆叉搜索树，那么我们不能直接判断出它在左⼦树，还是在右⼦树。不如暴⼒点，先在左⼦树中找，如果右⼦树没找到，说明都在左⼦树，如果左⼦树没找到，说明都在右⼦树，如果两个都分别存在，说明当前节点就是他们的⽗节点。

1. public class Solution68 {
2.     public int lowestCommonAncestor(TreeNode root, int p, int q) {
3.         TreeNode result = commonAncestor(root, p, q);
4.         return result == null ? -1 : result.val;
5.     }
6.     public TreeNode commonAncestor(TreeNode root, int p, int q) {
7.         if (null == root) {
8.             return null;
9.         }
10.         if (root.val == p || root.val == q) {
11.             return root;
12.         }
13.         TreeNode left = commonAncestor(root.left, p, q);
14.         TreeNode right = commonAncestor(root.right, p, q);
15.         if (left == null) {
16.             return right;
17.         } else if (right == null) {
18.             return left;
19.         } else {
20.             return root;
21.         }
22.     }
23. }

复制代码

• 时间复杂度：O(n)，需要遍历整个树
  
• 空间复杂度：O(h)，递归栈深度
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！