interviewalgo
, , ,
Source
Edit
History

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

Introduction

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

Analysis

我们可以做一次后序遍历，在返回值中判断某个节点是否为 p 和 q 的祖先，当某个节点是p和q的公共祖先时，则直接返回。

由于 p 和 q 一定存在于给定的二叉树中，所以一定有解。
我们可以简化上面那个算法的返回值，直接利用返回的指针是否为空来判断在左右子树中是否发现了要查找的节点。

后序遍历
如果 root == p || root == q，有两种可能：

  1. 祖先节点就是 root
  2. 祖先节点不是 root，而是 root 的祖先，所以当遇到 root 时，就不需要向下遍历了，直接返回当前节点。

如果 root != p || root != q，那么则进行后序遍历，并返回左右子树遍历后返回值不为空的那个，如果都不为空，则表示在左右子树中分别查找到了 p 和 q，因此直接返回当前节点即可。

Implement

1
2
3
4
5
6
7
8
9
10
11
12
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) return nullptr;
    if (root == p || root == q) return root;

    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    TreeNode *res = nullptr;
    if (!left) res = right;
    else if (!right) res = left;
    else if (left && right) res = root;
    return res;
}