Skip to main content

1650. Lowest Common Ancestor of a Binary Tree III

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

Python​

Find root first then DFS​

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        root = p
        while root.parent:
            root = root.parent

        # Same as Leetcode 236.
        def dfs(node):
            if not node:
                return node

            if node.val == p.val or node.val == q.val:
                return node

            left = dfs(node.left)
            right = dfs(node.right)

            if not left or not right:
                return left if left else right

            return node

        return dfs(root)

Floyd's Algorithm​

  • 將從兩個node到root間的這條path做成looped Linked List

  • 用Floyd's Algorithm去找出重疊的節點

  • Time: # 不好算，但會是兩個節點間經過root連結起來的這條Linked List與兩個節點的差

  • Space: O(1)

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        p1, p2 = p, q
        while p1 != p2:
            p1 = p1.parent if p1.parent else q
            p2 = p2.parent if p2.parent else p

        return p1

Javascript​

var lowestCommonAncestor = function(p, q) {
    function findRoot(node) {
        return node.parent ? findRoot(node.parent) : node;
    }

    const root = findRoot(p);
    let res = null;
    const recursive = (node) => {
        if (!node) return false;
        const isLeft = recursive(node.left);
        const isRight = recursive(node.right);

        const isMid = node.val === p.val || node.val === q.val;
        if (isLeft && isRight || isLeft && isMid || isRight && isMid) {
            res = node;
            return;
        }
        return isLeft || isRight || isMid;
    }

    recursive(root);
    return res;
};