236. Lowest Common Ancestor of a Binary Tree

# time O(N) space O(H)  H: stack 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# time O(N)  space O(N)
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """  tc O(N) sc O(H)
        main idea: 3 cases --    (1) p is parent of q (2) q is parent of p (3) there is common parent of p, q 
        1. termination condition:  current root node  is None/  current root is node p  or node q
        2. for current root node recursively go deeper of the tree, get return val from its subtree 
        3. based on if p, q come from the same subtree, return different LCA accordingly  
        """
        
        if not root:
            return None
        if root == p or root == q :
            return root 
        leftParent = self.lowestCommonAncestor(root.left,p,q)
        rightParent =  self.lowestCommonAncestor(root.right,p,q)
        if leftParent and rightParent:
            return root
        elif  rightParent:
            return rightParent
        elif  leftParent :
            return leftParent

# time O(N)  space O(N)
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
      class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        1. inorder traversal to get p and  q, record each node's parent node 
        2. start from node p and cache its all ancestor 
        3. back trace node q's ancestor and check if its ancestor appeared in p's ancestor 
            tc O(N)   sc O(N) 
        """ 
        st = [root]
        parent = {root:None}
        while not(p in parent and q in parent):
            node = st.pop()
            if node.left:
                st.append(node.left)
                parent[node.left] = node
            if node.right:
                parent[node.right] = node
                st.append(node.right)
        
        seen = set()
        cur = p
        while cur:
            seen.add(cur)
            cur = parent[cur]
            
        
        cur2 = q 
        while cur2 not in seen:
            cur2 = parent[cur2]
        return cur2

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        1.cornor case   
        2. use stack to cache path and parent node, in order traverse both p ,q 
        3. start from root, find the first appeared node in both pathp and pathq 
        """
        if not root or root == p or root == q:
            return root
        st = [(root,[root])]
        pathp, pathq = [],[]
        
        while not(pathp and pathq):
            node,path  = st.pop()
            if node == p:
                pathp = path[:]
            if node == q:
                pathq = path[:] 
            if node.left:
                st.append((node.left,path+[node.left]))
            if node.right:
                st.append((node.right,path+[node.right]))
        
        i,n = 0, min(len(pathq),len(pathp))
        while i < n and pathq[i] is pathp[i]:
            res = pathq[i]
            i += 1
        return res 

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        assuming all nodes are unique 
        1.use DFS to search for p and q, and record both p,q's path, 
        2.compare two paths and find the lowest common ancestor
        """
        st,ppath,qpath = [],[],[]
        while True:
            if root.left:
                st.append(root)
                root.left,root = None, root.left
            elif root.right:
                st.append(root)
                root.right,root = None, root.right
            else:
                if root == p:
                    ppath = st[:]
                    ppath.append(root)
                if root == q:
                    qpath = st[:]
                    qpath.append(root)
                if ppath and qpath:
                    break 
                root = st.pop()
        i,len_path = 0, min(len(ppath),len(qpath))
        while i < len_path and ppath[i] is qpath[i]:
            
            res = ppath[i]
            i += 1
        return res