Python ITERATIVE solution


  • 0

    Sometimes interviewers ask us about iterative version of recursive algorithm, so here we go.

    def is_done(node, depths):
        left, right = node.left, node.right
        return (not left or left in depths) and (not right or right in depths)
        
    class Solution(object):
        def isBalanced(self, root):
            stack, depths = [root], {}
            while stack:
                node = stack.pop()
                if not node: continue
                if is_done(node, depths):
                    left  = 0 if not node.left  else depths[node.left]
                    right = 0 if not node.right else depths[node.right]
                    if abs(left - right) > 1: return False
                    depths[node] = 1 + max(left, right)
                else:
                    if node.left and node.left not in depths:
                        stack += node, node.left
                    else:
                        stack += node, node.right
            return True
    

  • 1

    Just a quick hack:

    def isBalanced(self, root):
        nodes = [root]
        for node in nodes:
            if node:
                nodes += node.left, node.right
        depth = {None: 0}
        for node in reversed(nodes):
            if node:
                left, right = depth[node.left], depth[node.right]
                if abs(left - right) > 1:
                    return False
                depth[node] = 1 + max(left, right)
        return True

  • 0

    @StefanPochmann haha that's fun. I came up with another one.

    class Solution(object):
        def isBalanced(self, root):
            stack, node, last, depths = [], root, None, {}
            while stack or node:
                if node:
                    stack.append(node)
                    node = node.left
                else:
                    node = stack[-1]
                    if not node.right or last == node.right:
                        node = stack.pop()
                        left, right  = depths.get(node.left, 0), depths.get(node.right, 0)
                        if abs(left - right) > 1: return False
                        depths[node] = 1 + max(left, right)
                        last = node
                        node = None
                    else:
                        node = node.right
            return True
    
    

Log in to reply
 

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