Solution 1 DFS

  • t-complexity: O(N) N is number of nodes

  • s-complexity: O(N) in worst case, recursion depth is N

three cases for root is p and q's lowest common ancester:

  1. p and q are in root's sub-trees, and is not in same side

  2. p == root, q is in root's left or right sub-tree

  3. q == root, p is in root's left or right sub-tree

Previous0236_Lowest_Common_Ancestor_of_a_Binary_TreeNext0237_Delete_Node_in_a_Linked_List

Last updated