My python recursion and iteration solution. easy and fast


  • 7
    G

    Iteration:

    enter code hereclass Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        while root:
            if not root or root==p or root==q:
                return root
            if self.isnode(p,q):
                return p
            if self.isnode(q,p):
                return q
            if self.isnode(root.left,p) and self.isnode(root.left,q):
                root=root.left
            if self.isnode(root.right,p) and self.isnode(root.right,q):
                root=root.right
            else:
                return root
                
        
    def isnode(self,mother,child):
        if mother:
            if mother==child:
                return True
            else:
                return self.isnode(mother.left,child) or self.isnode(mother.right,child)
        return False        
    

    recursion:

    enter code hereclass Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        
        if not root or root==p or root==q:
            return root
            
        if self.isnode(p,q):
            return p
        if self.isnode(q,p):
            return q
            
        if self.isnode(root.left,p) and self.isnode(root.left,q):
            return self.lowestCommonAncestor(root.left, p, q)
        elif self.isnode(root.right,p) and self.isnode(root.right,q):
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root
                
        
    def isnode(self,mother,child):
        if mother:
            if mother==child:
                return True
            else:
                return self.isnode(mother.left,child) or self.isnode(mother.right,child)
        return False

Log in to reply
 

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