LCA (Lowest Common Ancestor) 中文名稱"最近公共祖先"。是指在樹(shù)中，兩個(gè)節(jié)點(diǎn)的最近的公共根。LeetCode里面的236題講的就是這個(gè)。

實(shí)現(xiàn)

方法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) { // 因?yàn)閞oot是從上往下的，所以這里對(duì)應(yīng)的情況像是p完全在q的上面，或者q完全在p的上面
        return root;
    }
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left == null) { // 左邊沒(méi)有l(wèi)ca
        return right;
    }
    if (right == null) { // 右邊沒(méi)有l(wèi)ca
        return left;
    }
    return root; // 左右都有找到match，說(shuō)明pq一個(gè)match了左，一個(gè)match了右，那lca其實(shí)是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的上面的路徑都記錄了下來(lái)
        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都記錄下來(lái)
        p = parents.get(p); // 把p變成它的parent
    }
    while (!ancestors.contains(q)) { // 還沒(méi)有遇到一樣的parent
        q = parents.get(q);
    }
    return q;
}

時(shí)間復(fù)雜度都是O(n)
空間復(fù)雜度都是O(h)，最情況是O(n)

相關(guā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/