236. Lowest Common Ancestor of a Binary Tree

source: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Question

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

初想法

第一想法是每个节点都持有一个不同引用地址的数组，这个数组含有此节点的所有父节点。

这个想法的问题是每次递归都要新建一个数组，空间复杂度O(n2), 导致会OOM.

 var lowestCommonAncestor = function(root, p, q) {
    let pParents;
    let qParents;
    const dfs = (node, list, parents) => {
        if (node) {
            list.push(node);
            parents.push(node);
            if (node === p) pParents = parents;
            if (node === q) qParents = parents;
            if (list.includes(p) && list.includes(q)) {
                return null
            }
            return dfs(node.left, list, [...parents]) || dfs(node.right, list, [...parents]);
        }
    };
    return dfs(root, [], []);
};

改进

分别从左右节点找目标子节点：

• 如果两个子节点都找到了，那么自身肯定是他们的公共父节点
• 如果只找到了一边的节点，说明两个目标子节点都在这一边，直接选取自身作为公共父节点

var lowestCommonAncestor = function(root, p, q) {
    const dfs = node => {
        if (!node || node === p || node === q) return node;
        const left = dfs(node.left);
        const right = dfs(node.right);
        return left && right ? node : left || right;
    };
    return dfs(root);
};

pub fn lowest_common_ancestor(
    root: Option<Rc<RefCell<TreeNode>>>,
    p: Option<Rc<RefCell<TreeNode>>>,
    q: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
    fn dfs(
        node: Option<Rc<RefCell<TreeNode>>>,
        p_val: i32,
        q_val: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(x) = node {
            if x.borrow().val == p_val || x.borrow().val == q_val {
                return Some(Rc::clone(&x));
            }
            let left = dfs(x.borrow_mut().left.take(), p_val, q_val);
            let right = dfs(x.borrow_mut().right.take(), p_val, q_val);
            if left.is_none() {
                right
            } else if right.is_none() {
                left
            } else {
                Some(Rc::clone(&x))
            }
        } else {
            None
        }
    }
    dfs(root, p.unwrap().borrow().val, q.unwrap().borrow().val)
}

并查集

总结

这题其实并不难，第一反应用dfs也是没问题的，但是对于如何确定公共子节点block住了。

每道bst的题目除了通用的search部分，也要抓住他们核心的逻辑实现部分。