Critique my python solution?


  • 0
    S
    class Solution:
        # @param {TreeNode} root
        # @param {TreeNode} p
        # @param {TreeNode} q
        # @return {TreeNode}
        def lowestCommonAncestor(self, root, p, q):
            if root.left:
                r = self.lowestCommonAncestor(root.left, p, q)
                if r: return r
    
            if root.right: 
                r = self.lowestCommonAncestor(root.right, p, q)
                if r: return r
            
            (has_p, has_q) = self.has_target_descendant(root, p, q)
            if has_p and has_q: return root
            return None
            
        def has_target_descendant(self, root, p, q):
            has_p, has_q = root == p, root == q
            
            if root.left:
                (branch_has_p, branch_has_q) = self.has_target_descendant(root.left, p, q)
                has_p = branch_has_p or has_p
                has_q = branch_has_q or has_q
    
            if root.right:
                (branch_has_p, branch_has_q) = self.has_target_descendant(root.right, p, q)
                has_p = branch_has_p or has_p
                has_q = branch_has_q or has_q
    
            
            return (has_p, has_q)
    

    I don't think this is a great solution. The running time should be O(n^2) as I do a post-order traversal and each time I check if every child nodes


  • 0

    I'm not sure about the speed (it's 5am and this is complicated :-), but you can remove some parentheses and duplication:

    class Solution:
        
        def lowestCommonAncestor(self, root, p, q):
            for kid in root.left, root.right:
                if kid:
                    r = self.lowestCommonAncestor(kid, p, q)
                    if r: return r
            return root if all(self.has_target_descendant(root, p, q)) else None
    
        def has_target_descendant(self, root, p, q):
            has_p, has_q = root == p, root == q
    
            for kid in root.left, root.right:
                if kid:
                    branch_has_p, branch_has_q = self.has_target_descendant(kid, p, q)
                    has_p = branch_has_p or has_p
                    has_q = branch_has_q or has_q
    
            return has_p, has_q
    

    It's also simpler to search just one node at a time, and it even ran faster on the OJ:

    class Solution:
        
        def lowestCommonAncestor(self, root, p, q):
            for kid in root.left, root.right:
                if kid:
                    r = self.lowestCommonAncestor(kid, p, q)
                    if r: return r
            return root if self.has(root, p) and self.has(root, q) else None
    
        def has(self, root, node):
            return root and (root == node or
                             self.has(root.left, node) or
                             self.has(root.right, node))
    

Log in to reply
 

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