A fast recursive method avoid unnecessary work


  • 0
    Y

    The recursive method return a tuple, the first one is a TreeNode, the second one is a boolean flag. If the flag is true, it means we've already found the LCA, so we don't have to look into the other nodes we haven't visited.

    # Definition for a binary tree node.
       # class TreeNode:
       #     def __init__(self, x):
       #         self.val = x
       #         self.left = None
       #         self.right = None
    
    class Solution:
        # @param {TreeNode} root
        # @param {TreeNode} p
        # @param {TreeNode} q
        # @return {TreeNode}
        def lowestCommonAncestor(self, root, p, q):
            return self.commonAncestorHelper(root,p,q)[0]
        
    
        def commonAncestorHelper(self,root,p,q):
            if root==None:
                return None,False
            rightRes=self.commonAncestorHelper(root.right,p,q)
            if rightRes[1]==True:
                return rightRes
            if rightRes[0]!=None and (root==p or root==q):
                return root,True
            leftRes=self.commonAncestorHelper(root.left,p,q)
            if leftRes[1]==True:
                return leftRes
            if leftRes[0]!=None and (root==p or root==q):
                return root,True
            if rightRes[0] and leftRes[0]:
                return root,True
            if root==q or root==p:
                return root,False
            return rightRes[0] or leftRes[0],False

Log in to reply
 

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