# A fast recursive method avoid unnecessary work

• 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``````

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