[LeetCode] 问题系列 - LCA: Lowest Common Ancestor 问题

LCA (Lowest Common Ancestor) 中文名称"最近公共祖先"。是指在树中，两个节点的最近的公共根。LeetCode里面的236题讲的就是这个。

实现

方法1：recursion

public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == null || q == null) {
        return null;
    }
    if (root == p || root == q) { // 因为root是从上往下的，所以这里对应的情况像是p完全在q的上面，或者q完全在p的上面
        return root;
    }
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left == null) { // 左边没有lca
        return right;
    }
    if (right == null) { // 右边没有lca
        return left;
    }
    return root; // 左右都有找到match，说明pq一个match了左，一个match了右，那lca其实是root
}

方法2：iteration

public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    Map<TreeNode, TreeNode> parents = new HashMap<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    parents.put(root, null);
    stack.push(root);

    while (!parents.containsKey(p) || !parents.containsKey(q)) { // 把pq的上面的路径都记录了下来
        TreeNode node = stack.pop();
        if (node.left != null) {
            parents.put(node.left, node);
            stack.push(node.left);
        }
        if (node.right != null) {
            parents.put(node.right, node);
            stack.push(node.right);
        }
    }

    Set<TreeNode> ancestors = new HashSet<>();
    while (p != null) {
        ancestors.add(p); // 把p的所有parent都记录下来
        p = parents.get(p); // 把p变成它的parent
    }
    while (!ancestors.contains(q)) { // 还没有遇到一样的parent
        q = parents.get(q);
    }
    return q;
}

时间复杂度都是O(n)
空间复杂度都是O(h)，最情况是O(n)

相关题目

124 Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/

235 Lowest Common Ancestor of a Binary Search Tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

236 Lowest Common Ancestor of a Binary Tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/