[Leetcode] 236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

initial

I didnt know how and especially like this kind of case

   0 (Root)
     /
    1
   /
  2
 / \
3   4
/     \
5       6

Lets say p and q are 5 and 6. 2 is the right answer, not 0. So how?

The end recursion conditions should first be that if root is None/p/q, then we return root. This is cuz if left and right traversal all have legitamate values (not none but p and q), then that means the current root node is the answer.

For example if at current root node is 3 and left's result is 5 and right's result is None, then we just traverse this value 5 back up. Same for node 4. Then at root 2, since we have legit left and right values, 2 is the answer. We then return this value 2 immeidately up the call stack.

solution

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        def find(node,p,q):
            if not node or node==p or node==q:
                return node
            left=find(node.left,p,q)
            right=find(node.right,p,q)
            if left and right:
                return node
            elif left:
                return left
            elif right:
                return right
        return find(root,p,q)

complexity

o(n) time cuz all nodes traeversed once
o(h) space, o(n) if skewed, o(log n) if balanced