236. Lowest Common Ancestor of a Binary Tree
# Medium
Two methods:
Harder to implement, but easy to understand. Every node returns information of <ancestor, numOf(p,q)>, which means:
if in this node's tree, don't find (p, q), then return <NULL, 0>.
if find one of (p, q), then return <NULL, 1>.
if find both of (p, q), then return <root, 2>. ⚠️this node may be p or q, count it as well.
Easy to implement, but harder to understand. From top to bottom, very recursive return:
if only node.left or node.right contains (p, q), continue returning the returnValue of lower level.
if both of node.left and node.right contian p and q, they must be separated in left and right subtree, then return node, this is the real ancestor.
for higher level recursive, this node will continue passing up, because only one of any its parents' child has no-NULL returnValue.
Solution 1:
edge case in main function.
traversal each node from bottom to up, to pass <ancestor, numOf(p, q)>.
return ancestor in main function.
Last updated