I don't know what's going on. I'll admit if my solution is 100% correct, then the test cases might be too easy...
class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if (p == root or q == root) or (left and right): return root else: return left if left else right
It took me a while to figure out how it works. The method basically pre-assumes that both p and q already resided in the given tree thus even if there is only one of p,q existing in the tree, the method still returns either p or q.
Therefore the correctness of this method is automatically guaranteed.
However, if one of the given p,q is absent from the tree at root, the method is not always correct. For example, when root is only q and both p and q are given.