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