题目

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

百度百科中最近公共祖先的定义为：“对于有根树 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, 105] 内。

  • -109 <= Node.val <= 109

  • 所有 Node.val 互不相同 。

  • p != q

  • p 和 q 均存在于给定的二叉树中。

  • -109 <= Node.val <= 109

  • 所有 Node.val 互不相同 。

  • p != q

  • p 和 q 均存在于给定的二叉树中。

解题思路

首先dfs(deep first search)二叉树，使用后序遍历，若节点为空或者遇到p或者q时返回。

将结果保存在left 和 right中

然后根据以下不同情况做出不同反映即可：

  1. left 和 right 都不为空：返回root，此时以及找到公共祖先了
  2. left 为空 right不为空：返回right
  3. left 不为空 right 为空：返回left
  4. 返回：None

代码

Python

1
2
3
4
5
6
7
8
9
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or 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
        if left is None and right: return right
        elif left and right is None: return left
        else: return None

C++

1
2
3
4
5
6
7
8
9
10
11
12
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 root;
        if (left == NULL && right != NULL) return right;
        else if (left != NULL && right == NULL) return left;
        else return NULL;
    }
};

Go

 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if (root == nil || root == p || root == q) {return root}
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }else if left == nil && right != nil {
        return right
    }else if left != nil && right == nil {
        return left
    } else {
        return nil
    }
}