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

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件：
        // 1) root 为空，说明这条分支没找到目标
        // 2) root == p 或 root == q，说明找到其中一个目标节点
        if (root == null || root == p || root == q) return root;

        // 去左子树寻找 p/q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 去右子树寻找 p/q
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 若左右子树都非空，说明 p 和 q 分别位于两侧，当前节点即最近公共祖先
        if (left != null && right != null) return root;

        // 否则只可能在一侧找到目标（或都没找到），把非空结果继续向上返回
        return left != null ? left : right;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // parent 记录每个节点的父节点：child -> parent
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        // 栈用于遍历整棵树并建立 parent 映射
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 根节点的父节点记为 null
        parent.put(root, null);
        // 根节点入栈
        stack.push(root);

        // 遍历整棵树，构建完整父指针表
        while (!stack.isEmpty()) {
            // 弹出当前节点
            TreeNode node = stack.pop();
            // 若左孩子存在，记录其父节点并入栈
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            // 若右孩子存在，记录其父节点并入栈
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }

        // ancestors 存储从 p 一路向上的所有祖先（含 p 自身）
        Set<TreeNode> ancestors = new HashSet<>();
        // 从 p 向上走到根，把路径节点全部加入集合
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }

        // 从 q 向上走，第一个出现在 ancestors 中的节点就是最近公共祖先
        while (!ancestors.contains(q)) {
            q = parent.get(q);
        }
        // 返回最近公共祖先
        return q;
    }
}