Clear and concise python solution


  • 0
    A

    Clear and concise python recursive solution. Use infinity to mark a left or right subtree as invalid, and the infinity will propagate up the recursive stack. O(N) time complexity (though not entirely convinced of this on balanced vs unbalanced binary trees, maybe someone can help out here with clear explanation of runtime in both cases).

        def isBalanced(self, root):
            def check(root):
                if not root:
                    return 0
                left,right = check(root.left),check(root.right)
                if abs(left-right) > 1:
                    return float("inf")
                return 1+max(left,right)
            return check(root) != float("inf")
    

Log in to reply
 

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