236. Lowest Common Ancestor of a Binary Tree

Leetcode

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

題目

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).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

解答

• 方法一

DFS

找到 LCA 的關鍵有兩點

1. 左邊子節點及右邊子節點分別找到 p, q

2. 本身節點為 p, q 其中一個，剩下的一個在左邊 or 右邊子節點

var lowestCommonAncestor = function(root, p, q) {
    let ans;
    
    const dfs = (node) => {
        if (!node) return false;
        
        const isLeftFound = dfs(node.left) ? 1 : 0;
        const isRightFound = dfs(node.right) ? 1 : 0;
        // 自己本身為 p or q 節點
        const isSelfFound = (node === p || node === q) ? 1 : 0;
        
        if (isLeftFound + isRightFound + isSelfFound >= 2) ans = node;
        if (isLeftFound || isRightFound || isSelfFound) return true;
        return false;
    }
    
    dfs(root);
    return ans;
};

Runtime: 98 ms, faster than 69.39% of JavaScript online submissions for Lowest Common Ancestor of a Binary Tree.

Memory Usage: 51.5 MB, less than 84.43% of JavaScript online submissions for Lowest Common Ancestor of a Binary Tree.

• 方法二

BST - 紀錄父節點方法

當 p, q 找到時，要找到 LCA 的方式就是要把遍歷尋找 p, q 時，把所有的父節點都用 hash map 記錄下來 (parentMap)，接著再去比對 p, q 各自的父節點，找出共有的那個即是答案

var lowstCommonAncestor = function(root, p, q) {
    const stack = [root];
    // 根節點的父節點指向 null
    const parentMap = new Map([
        [root, null]
    ]);
    
    // 只要還沒存入 p, q 的父節點就繼續找
    while (!parentMap.has(p) || !parentMap.has(q)) {
        const node = stack.pop();
        
        if (node.right) {
            parentMap.set(node.right, node);
            stack.push(node.right);
        }
        if (node.left) {
            parentMap.set(node.left, node);
            stack.push(node.left);
        }
    }
    
    // 存放 p, q 的父節點
    const ancestors = [];
    
    while (p) {
        // 將 p 的父節點全部塞到 ancestors 中
        ancestors.push(p);
        p = parentMap.get(p);
    }
    
    // 當 q 在 ancestors 中時，此時就找到了 p, q 共有的父節點
    while (!ancestors.includes(q)) {
        q = parentMap.get(q);
    }
    
    return q;
};

Runtime: 188 ms, faster than 6.41% of JavaScript online submissions for Lowest Common Ancestor of a Binary Tree.

Memory Usage: 50.8 MB, less than 99.26% of JavaScript online submissions for Lowest Common Ancestor of a Binary Tree.