# 120ms Python tricky solution

• Look here!!

This figure shows the value of count on entry to each node:

Number of target nodes visited on entry to each node

And this figure shows the value of count on exit from each node:

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
``````

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