236. 二叉树的最近公共祖先 ——【Leetcode每日一题】

亦凉 2024-03-23 15:47 18阅读 0赞

### 236. 二叉树的最近公共祖先 ###

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

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

##### 示例 1： #####

![在这里插入图片描述][9c5019bf0ccf408ab46bca606b22084f.png]

> 输入：root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 1  
> 输出：3  
> 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

##### 示例 2： #####

![在这里插入图片描述][533186fd453a4cf79bc64f68144acbc5.png]

> 输入：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 , 1 0 5 \] \[2, 10^5\] \[2,105\] 内。
 *   − 1 0 9 < = N o d e . v a l < = 1 0 9 -10^9 <= Node.val <= 10^9 −109<=Node.val<=109
 *  所有 `Node.val` 互不相同 。
 *  `p != q`
 *  `p` 和 `q` 均存在于给定的二叉树中。

#### 思路：（递归 —— 通俗易懂） ####

该树不是二叉搜索树，所以题解与[235. 二叉搜索树的最近公共祖先][235.]不同:

**法一：后序遍历**

找最近公共祖先，最先想到的应该是从树的**叶子节点** **从下往上找**：找到第一个子树，既包节点括`p`，有包括节点`q`的根节点，即为我们要找的**最近公共祖先**：

节点`p`和`q`既可以是**最近公共祖先**，也可以在**最近公共祖先**的**左右子树上，这需要分别判断**；

*  我们设一个全局变量`ans`保存我们要找的答案：**最近公共祖先**；
 *  如果当前节点是`p`和`q`的其中一个，就 **+1**，然后判断加上该节点的**左右子树的返回值**，如果等于2，即为答案；如果不等于2，则返回以该节点为根节点的子树中节点等于`p`或`q`的个数。
 *  递归即可得到答案！

**法二：先序遍历**

该题也可以**从上往下找**：

*  首先判断根节点是否等于`p`或`q`，如果**相等**则返回该节点；
 *  如果**不等**则递归该节点的左右子树：
    
     *  如果左右子树的返回值都不为空，则该节点就是**最近公共祖先**，返回当前节点；
     *  如果左右子树返回返回值中有一个不为空，则返回不为空的返回值；
     *  如果都为空，则以该节点为根节点的子树中没有一个节点等于`p`或`q`，返回`null`。
 *  最后的返回值即为 **最近公共祖先**。

#### 代码：(Java、C++) ####

**法一：后序遍历**  
**Java**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private TreeNode ans = null;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            dfs(root, p, q);
            return ans;
        }
        public int dfs(TreeNode root, TreeNode p, TreeNode q){
        
            if(root == null) return 0;
            int left = dfs(root.left, p, q);
            int right = dfs(root.right, p, q);
            if(p == root || q == root){
        
                left++;
            }
            if(left + right == 2){
        
                ans = root;
                return 0;
            }
            return left + right;
        }
    }

**C++**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        
    public:
        TreeNode* ans = nullptr;
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            dfs(root, p, q);
            return ans;
        }
        int dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        
            if(root == nullptr) return 0;
            int left = dfs(root->left, p, q);
            int right = dfs(root->right, p, q);
            if(p == root || q == root){
        
                left++;
            }
            if(left + right == 2){
        
                ans = root;
                return 0;//置0
            }
            return left + right;
        }
    };

**法二：先序遍历**  
**Java**

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);
            return left == null ? right : right == null ? left : root;
        }
    }

**C++**

class Solution {
        
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            if(root == nullptr || root == p || root == q) return root;
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            TreeNode* right = lowestCommonAncestor(root->right, p, q);
            return left == nullptr ? right : right == nullptr ? left : root;
        }
    };

##### 运行结果： #####

![在这里插入图片描述][06a9862f68084aa9a145d2a25ca7abfb.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n) ： 其中 `n` 为二叉树节点数；最差情况下，需要递归遍历树的所有节点。
 *  **空间复杂度**： O ( n ) O(n) O(n) ： 最差情况下，递归深度达到`n`，系统使用  O ( n ) O(n) O(n)大小的额外空间。

题目来源：[力扣。][Link 2]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[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
[9c5019bf0ccf408ab46bca606b22084f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/23bcddf7e84d4bbcbd8112c261fba903.png
[533186fd453a4cf79bc64f68144acbc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/b859354d850248f4a69907f788b6889f.png
[235.]: https://blog.csdn.net/weixin_43412762/article/details/130285482?spm=1001.2014.3001.5502
[06a9862f68084aa9a145d2a25ca7abfb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/63342c2951ef4df3986d476e1b2dc545.png
[Link 2]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
[leetCode]: http://t.csdn.cn/kQLJO