Why nested recursive function isn't passing?


  • 2
    B

    Change the check_unbalanced function definition to Solution class, my code passes.
    Otherwise, it reaches Max Recursion Limit.

    Anyone knows why?

    class Solution:
        # @param root, a tree node
        # @return a boolean
        def isBalanced(self, root):
            UnbalancedException = type('UnbalancedException', (Exception,), {})
            def check_unbalanced(node):
                if node is None:
                    return 0
                left_height = check_unbalanced(node.left)
                right_height = check_unbalanced(node.right)
                if abs(left_height - right_height) > 1:
                    raise UnbalancedException
                else:
                    return 1 + max(left_height, right_height)
            try:
                check_unbalanced(root)
                return True
            except UnbalancedException:
                return False
    

    For your reference, the following code does pass:

    class Solution:
        UnbalancedException = type('UnbalancedException', (Exception,), {})
        def check_unbalanced(self, node):
            if node is None:
                return 0
            left_height = self.check_unbalanced(node.left)
            right_height = self.check_unbalanced(node.right)
            if abs(left_height - right_height) > 1:
                raise Solution.UnbalancedException
            else:
                return 1 + max(left_height, right_height)
        # @param root, a tree node
        # @return a boolean
        def isBalanced(self, root):
            try:
                self.check_unbalanced(root)
                return True
            except Solution.UnbalancedException:
                return False

Log in to reply
 

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