python - lowest common ancestor in binary tree


  • 0
    S
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):        
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            
            # 1. bfs to search p and q
            queue = [root]
            parent = {root:None}
            while p not in parent or q not in parent:
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                    parent[node.left] = node
                if node.right:
                    queue.append(node.right)
                    parent[node.right] = node
            
            # 2. nullify all ancestors of p
            curr = p
            while curr:
                tmp = parent[curr]
                parent[curr] = None
                curr = tmp
            
            # 3. start walking back from q till a None is encountered
            curr = q
            while parent[curr]:
                curr = parent[curr]
            
            return curr
            
                    
    

Log in to reply
 

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