Python solution by recursion.


  • 0
    L

    Using dfs to go through all the nodes and their parents. Find out one node's parents list and search another node's parents until we find the LCA.

    class Solution(object):
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            if p == q:  return p
            if p == root or q == root:  return root
            parent_dic = {}
            def dfs(root,parent_dic):
                if root.left:
                    parent_dic[root.left] = root
                    dfs(root.left,parent_dic)
                if root.right:
                    parent_dic[root.right] = root
                    dfs(root.right,parent_dic)
                return 
            dfs(root,parent_dic)
            dummy = TreeNode(0)
            parent_dic[root],p_path = dummy,[]
            while(p != dummy):
                p_path.append(p)
                p = parent_dic[p]
            while(q != dummy):
                if q in p_path: return q
                else:   q = parent_dic[q]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.