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

题目描述

这是 LeetCode 上的 236. 二叉树的最近公共祖先 ，难度为 中等。

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

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

示例 1：

1
2
3
4
5
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

输出：3

解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

1
2
3
4
5
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

输出：5

解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
1
2
3
输入：root = [1,2], p = 1, q = 2

输出：1

提示：

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

DFS

常见的 LCA 问题。

设计 DFS 函数 boolean dfs(TreeNode cur, TreeNode t, List<TreeNode> path)：其中 cur 为当前处理到的节点，t 为需要找到的目的节点，path 为从根节点到当前节点 cur 所经过的路径。若能够以当前节点 cur 为根的子树包含目标节点 t，函数返回 true，否则返回 false。

调用函数分别传入 p 和 q 作为目标节点，从而得到从根节点到 p 和 q 的路径列表，遍历路径找到最后一个相同的节点即是答案。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> a = new ArrayList<>(), b = new ArrayList<>();
        dfs(root, p, a); dfs(root, q, b);
        TreeNode ans = null;
        for (int i = 0; i < Math.min(a.size(), b.size()) && a.get(i) == b.get(i); i++) ans = a.get(i);
        return ans;
    }
    boolean dfs(TreeNode cur, TreeNode t, List<TreeNode> path) {
        if (cur == null) return false;
        path.add(cur);
        if (cur == t || dfs(cur.left, t, path) || dfs(cur.right, t, path)) {
            return true;
        } else {
            path.remove(path.size() - 1);
            return false;
        }
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> a, b;
        dfs(root, p, a); dfs(root, q, b);
        TreeNode* ans = nullptr;
        for (int i = 0; i < min(a.size(), b.size()) && a[i] == b[i]; i++) ans = a[i];
        return ans;
    }
    bool dfs(TreeNode* cur, TreeNode* t, vector<TreeNode*>& path) {
        if (!cur) return false;
        path.push_back(cur);
        if (cur == t || dfs(cur->left, t, path) || dfs(cur->right, t, path)) {
            return true;
        } else {
            path.pop_back();
            return false;
        }
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(cur, t, path):
            if not cur:
                return False
            path.append(cur)
            if cur == t or dfs(cur.left, t, path) or dfs(cur.right, t, path):
                return True
            else:
                path.pop()
                return False
        a, b = [], []
        dfs(root, p, a)
        dfs(root, q, b)
        ans = None
        for i in range(min(len(a), len(b))):
            if a[i] == b[i]:
                ans = a[i]
        return ans

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    const a = [], b = [];
    dfs(root, p, a);
    dfs(root, q, b);
    let ans = null;
    for (let i = 0; i < Math.min(a.length, b.length) && a[i] === b[i]; i++) ans = a[i];
    return ans;
}
function dfs(cur: TreeNode | null, t: TreeNode | null, path: TreeNode[]): boolean {
    if (!cur) return false;
    path.push(cur);
    if (cur === t || dfs(cur.left, t, path) || dfs(cur.right, t, path)) {
        return true;
    } else {
        path.pop();
        return false;
    }
}

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.236 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。