120ms Python tricky solution


  • 0
    H

    Look here!!

    This figure shows the value of count on entry to each node:
    enter image description here

    Number of target nodes visited on entry to each node

    And this figure shows the value of count on exit from each node:
    enter image description here

    Number of target nodes visited on exit from each node

    You'll see that all the common ancestors of the two nodes have count = 0 on entry and count = 2 on exit (and only common ancestors have this property).

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Status(object):
        pass
    
    
    class Solution(object):
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            status = Status()
            status.count = 0
            status.ancestor = None
    
            def traveler(node):
                if not node:
                    return node
    
                entity = status.count
                if node in (p, q):
                    status.count += 1
    
                traveler(node.left)
                traveler(node.right)
    
                if entity == 0 and status.count == 2 and status.ancestor is None:
                    status.ancestor = node
    
            traveler(root)
            return status.ancestor
    

Log in to reply
 

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