【leetcode236】二叉树的最近公共祖先

一时失言乱红尘 2022-11-16 15:23 204阅读 0赞

## 题目描述 ##

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

**提示：**

*  树中节点数目在范围 \[2, 10^5\] 内。
 *  \-10^9<= Node.val <= 10^9
 *  所有 Node.val 互不相同 。
 *  p != q
 *  p 和 q 均存在于给定的二叉树中。

示例：

> 输入：root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 4  
> 输出：5  
> 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

![在这里插入图片描述][20210407225835558.png_pic_center]

## 解题思路 ##

对于二叉树的问题，我们通常要往递归的思路上去思考。思考递归的关键在于找到子问题，和终止条件。

在本题中子问题是：对于一个根节点，

*  如果节点p和节点q 都在左子树上，那么应该到左子树上去寻找最近公共祖先；
 *  如果节点p和节点q都在右子树上，那么应该到右子树上去寻找最近公共祖先；
 *  如果节点p和节点q 一个在左子树节点，一个在右子树节点，那么根节点就是最近公共祖先。

终止条件是：对于一个根节点，

*  如果根节点为空，那么就返回空，说明没找到任何一个节点。
 *  如果根节点的值与任何一个节点的值相等，就返回根节点，表示找到了其中一个节点。

class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            
            if(!root) return NULL;
            if(root->val ==  q->val || root->val == p->val){
                return root;
            }
    
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
            if(left && right){
                return root;
            }else if(!left && !right){
                return NULL;
            }else if(left && !right){
                return left;
            }else{
                return right;
            }
        }
    };

## 复杂度分析 ##

*  时间复杂度：因为二叉树的节点有且只会被访问一次，因此时间复杂度为 O(N)。
 *  空间复杂度：递归本质上使用是系统栈，栈的深度取决于二叉树的高度。在最坏情况下二叉树为一条链，此时高度为 N，因此空间复杂度为 O(N)。

[20210407225835558.png_pic_center]: /images/20221022/0b193e61a00240ee82f2acd03460c449.png