剑指 Offer 68 - II. 二叉树的最近公共祖先

比眉伴天荒 2023-02-19 10:30 16阅读 0赞

### 剑指 Offer 68 - II. 二叉树的最近公共祖先 ###

*  剑指 Offer 68 - II. 二叉树的最近公共祖先
 *   *  思路
     *  代码

# 剑指 Offer 68 - II. 二叉树的最近公共祖先 #

https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

## 思路 ##

因为lowestCommonAncestor(root, p, q)的功能是找出以root为根节点的两个节点p和q的最近公共祖先，所以递归体分三种情况讨论：

1.  如果p和q分别是root的左右节点，那么root就是我们要找的最近公共祖先
2.  如果p和q都是root的左节点，那么返回lowestCommonAncestor(root.left,p,q)
3.  如果p和q都是root的右节点，那么返回lowestCommonAncestor(root.right,p,q)

边界条件讨论：

1.  如果root是null，则说明我们已经找到最底了，返回null表示没找到
2.  如果root与p相等或者与q相等，则返回root
3.  如果左子树没找到，递归函数返回null，证明p和q同在root的右侧，那么最终的公共祖先就是右子树找到的结点
4.  如果右子树没找到，递归函数返回null，证明p和q同在root的左侧，那么最终的公共祖先就是左子树找到

## 代码 ##

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if(root == null || root == p || root == q){ 
                return root;
            }
    
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            if(left == null && right == null) return null;
            if(left == null){ 
                return right;
            }
    
            if(right == null){ 
                return left;
            }
            return root;
            
        }
    }