📃 题目描述

题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

百度百科中最近公共祖先的定义为：“对于有根树 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 。因为根据定义最近公共祖先节点可以为节点本身

🔔 解题思路

递归

A 和 B 的最近公共祖先有三种情况：

1. A == root，则 A 是 B 的最近祖先（反之也一样）
2. A 和 B 都在左子树或者都在右子树上
3. A 和 B 分别位于 root 的左子树和右子树，则 root 就是最近公共祖先

直接递归做起来（后序遍历）

左: leftAncestor = 递归函数(root.left);
右: rightAncestor = 递归函数(root.right);
根: leftAncestor 与 rightAncestor 的逻辑处理(如果 leftAncestor 为空，rightAncestor 不为空，就返回 rightAncestor，说明目标节点是通过 rightAncestor 返回的，反之依然)

这里可能有点不好理解，为什么 left 为空，right 不为空，目标节点通过 right 返回呢？

这里放上代码随想录 (programmercarl.com) (opens new window)大佬的图片：

理解递归函数的返回值很重要：本题定义 lowestCommonAncestor 表示 root 节点的子树中是否包含 p 节点或 q 节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        // 情况 1：p 或者 q 为 root, 那么 root 就是最近公共祖先
        if (root == p || root == q) {
            return root;
        }
		
        // 情况 2：A 和 B 都在左子树或者都在右子树上
        
        // 左子树上找公共祖先
        TreeNode leftAncestor = lowestCommonAncestor(root.left, p, q);
        // 右子树上找公共祖先
        TreeNode rightAncestor = lowestCommonAncestor(root.right, p, q);

        // 左子树中没有找到公共祖先，那么一定在右子树中
        if (leftAncestor == null) {
            return rightAncestor;
        }
        // 右子树中没有找到公共祖先，那么一定在左子树中
        if (rightAncestor == null) {
            return leftAncestor;
        }

        // 情况 3：if(left != null and right != null) A 和 B 分别位于 root 的左子树和右子树，那么 root 就是最近公共祖先
        return root;
    }
}

注意下面这个结束条件不能少：

复杂度分析

• 空间复杂度：O(LogN)，递归调用的栈深度取决于二叉树的高度。二叉树最坏情况下为一条链，此时空间复杂度为 O(N)
• 时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。

DFS + 哈希表

我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。

算法

• 从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
• 从 p 节点开始不断往它的祖先移动，并记录已经访问过的祖先节点。
• 同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。

类似的题还有 863. 二叉树中所有距离为 K 的结点 (opens new window)

class Solution {
    // value 是 key 的父节点
    private Map<TreeNode, TreeNode> parnetMap = new HashMap<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        // 构造 parnet map:从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针
        findParents(root);

        // 存储已访问过的节点
        Set<TreeNode> visited = new HashSet<>();

        // 从 p 节点开始不断往它的祖先移动，并记录已经访问过的祖先节点
        while (p != null) {
            visited.add(p);
            p = parnetMap.get(p);
        }
        // 再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先
        while (q != null) {
            if (visited.contains(q)) {
                return q;
            }

            q = parnetMap.get(q);
        }

        return root;
    }   
    
	// dfs
    private void findParents(TreeNode root) {
        if (root.left != null) {
            parnetMap.put(root.left, root);
            findParents(root.left);
        }

        if (root.right != null) {
            parnetMap.put(root.right, root);
            findParents(root.right);
        }
    }
}

• 时间复杂度：O(N)
• 空间复杂度：O(N)，二叉树的所有节点有且只会被访问一次，从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N（相比于方法一要好），因此总的时间复杂度为 O(N)