My python solution with horrible run time


  • 0
    H
        #my solution
        class Solution:
            # @param {TreeNode} root
            # @return {boolean}
            def isBalanced(self, root):
                if root==None:
                    return True
                if not self.isBalanced(root.left) or not self.isBalanced(root.right):
                    return False
                if root.left==None:
                    return root.right==None or root.right.left==None==root.right.right
                if root.right==None:
                    return root.left.left==None==root.left.right
                stack=[]
                stack.append((root.left,0,1))
                lh=0
                while stack:
                    node,lev,h=stack.pop()
                    if node!=None and not lev:
                        stack.append((node,1,h))
                        stack.append((node.left,0,h+1))
                    elif node!=None and not lev-1:
                        stack.append((node,2,h))
                        stack.append((node.right,0,h+1))
                    if node!=None:
                        lh=max(lh,h)
                stack.append((root.right,0,1))
                rh=0
                while stack:
                    node,lev,h=stack.pop()
                    if node!=None and not lev:
                        stack.append((node,1,h))
                        stack.append((node.left,0,h+1))
                    elif node!=None and not lev-1:
                        stack.append((node,2,h))
                        stack.append((node.right,0,h+1))
                    if node!=None:
                        rh=max(rh,h)
                return abs(rh-lh)<2

  • 1
    C

    You can use BFS or DFS to solve this problem which is quite straight forward:

    # BFS
    def isBalanced(self, root):
        queue = []
        queue.append(root)
        while queue:
            curr = queue.pop(0)
            if curr:
                if abs(self.height(curr.left) - self.height(curr.right)) > 1:
                    return False
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
        return True 
      
    # DFS  
    def isBalanced(self, root):
        stack = []
        stack.append(root)
        while stack:
            curr = stack.pop()
            if curr:
                if abs(self.height(curr.left) - self.height(curr.right)) > 1:
                    return False
                if curr.right:
                    stack.append(curr.right)
                if curr.left:
                    stack.append(curr.left)
        return True
        
    def height(self, root):
        if not root:
            return 0
        return max(self.height(root.left), self.height(root.right)) + 1
    

Log in to reply
 

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