1644. Lowest Common Ancestor of a Binary Tree II

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

Python

Postorder Traversal

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        def post_order(node):
            if not node:
                return None, 0

            r_node, r_hits = post_order(node.right)
            l_node, l_hits = post_order(node.left)

            if node.val == p.val or node.val == q.val:
                return node, 1 + r_hits + l_hits

            if l_node and r_node:
                return node, r_hits + l_hits

            return (l_node, l_hits) if l_node else (r_node, r_hits)

        target_node, hits = post_order(root)

        return target_node if hits == 2 else None

Javascript

var lowestCommonAncestor = function(root, p, q) {
    if (!p || !q) return null;
    let res = null;
    const recursive = (node) => {
        if (!node) return null;
        let isLeft = recursive(node.left);
        let isRight = recursive(node.right);
        let isMid = node.val === p.val || node.val === q.val;
        if ((isMid && isRight) || (isMid && isLeft) || (isLeft && isRight)) {
            res = node;
        }
        return isLeft || isRight || isMid;
    }
    recursive(root);
    return res;
};