算法笔记_面试题_13.二叉树的最近公共祖先

╰+攻爆jí腚メ 2023-02-25 10:29 97阅读 0赞

# 题目 #

[面试题68 - II. 二叉树的最近公共祖先][68 - II.]

难度：简单

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

[百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”

例如，给定如下二叉树: root = \[3,5,1,6,2,0,8,null,null,7,4\]

![format_png][]

**示例 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。因为根据定义最近公共祖先节点可以为节点本身。

**说明:**

*  所有节点的值都是唯一的。
 *  p、q 为不同节点且均存在于给定的二叉树中。

# 答案 #

## 思路： ##

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

边界条件讨论：

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

## 代码： ##

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
         if (root == NULL || root == p || root == q) return root;
    	
         //分别检查左、右子树是否含有p或q
         TreeNode* leftTree = lowestCommonAncestor(root->left, p, q);
         TreeNode* rightTree = lowestCommonAncestor(root->right, p, q);
         
         if (leftTree == NULL) return rightTree;//左子树中没有，说明在右子树
         if (rightTree == NULL) return leftTree;//右子树中没有，说明在左子树
    	
         //如果在root的左右子树中都找到了
         return root;
    }

[68 - II.]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Link 1]: https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin
[format_png]: /images/20230209/407524bcb36a4aba9e47f82c53780646.png