当前位置：网站首页>leetcode:236. 二叉树的最近公共祖先

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

2022-07-06 15:53:00 【uncle_ll】

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

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

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

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

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

在这里插入图片描述

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

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

解法

递归: 先从根节点开始判断，如果根节点为空，或者某个查找元素为根节点，直接返回根节点；然后递归查找左子树，右子树，如果两个子树查找结果都不为空，表明p,q待查找的两个元素与左子树的根节点或者右子树的根节点相同，则二者的公共节点为该树的根节点；如果有一个子树的查找为空，则返回另外一个子树的查找结果；

代码实现

递归

python实现

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
           return root
        
        if root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:  # 二个子树的查找结果都不为空，说明拍，
            return root

        return left if left else 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        if (root == nullptr)
            return root;
        
        if (p == root || q == root)
            return root;
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr)
            return root;
        
        return left != nullptr ? left : right;

    }
};