Bit trick to solve LCA in Python


  • 0

    If the node is the Lowest Common Ancestor of the two given nodes p and q, this node must has one of the properties below:

    1. p and q are in the different subtree of this node
    2. node itself is one of p or q, and the other given node is in node's subtree

    That is, the LCA cannot have both p and q in the same subtree.
    Based on this fact, we can mark each node with a marker when we search for the target p and q.
    We mark the current node with 0b001 if the target node is in the current node's left subtree
    We mark the current node with 0b010 if the target node is in the current node's right subtree
    We mark the current node with 0b100 if the target node is the current node.

    Then we traverse all the nodes we marked, there would only be one marked node with a marker that has two bit 1, which would be exactly the LCA we want!

    def lowestCommonAncestor(self, root, p, q):
        def traverseMark(node, target):
            if not node:
                return False
            if node == target:
                markerHash[node] = markerHash.get(node, 0) | 4
                return True
            if traverseMark(node.left, target): # if target is in the left subtree
                markerHash[node] = markerHash.get(node, 0) | 1
                return True
            elif traverseMark(node.right, target): # if target is in the right subtree
                markerHash[node] = markerHash.get(node, 0) | 2
                return True
            return False
        
        markerHash = {}
        traverseMark(root, p)
        traverseMark(root, q)
        for node in markerHash:
            if markerHash[node] in (3,5,6):
                return node
        return None
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.