迭代解决方案寻找树是否平衡

Question

所以有人发布了他们的解决方案，但我发现它似乎没有工作，我发布了这个，但我想让它更容易被其他人访问。

的问题是，在“破解代码访谈”，这是第一棵树的问题，可随时进行其他建议（或证明我错了！）

Answer 1

这里的关键是，它是很难跟踪最终的路径和他们的高度与一个堆栈。

我最终做的是推动左右儿童的身高，检查他们是否在彼此之间，增加一个到最大值，然后弹出左侧和右侧后推入堆栈关闭。

我评论，所以我希望这是不够

/* Returns true if binary tree with root as root is height-balanced */ 
     boolean isBalanced(Node root) { 
      if(root == null) return false; 

      Deque<Integer> heights = new LinkedList<>(); 
      Deque<Node> trail = new LinkedList<>(); 
      trail.push(root); 

      Node prev = root; //set to root not null to not confuse when root is misisng children 

      while(!trail.isEmpty()) { 
       Node curr = trail.peek(); //get the next node to process, peek because we need to maintain trail until we return 

       //if we just returned from left child 
       if (curr.left == prev) { 
        if(curr.right != null) trail.push(curr.right); //if we can go right go 
        else { 
         heights.push(-1); //otherwise right height is -1 does not exist and combine heights 
         if(!combineHeights(heights)) return false; 
         trail.pop(); //back to parent 
        } 
       } 
       //if we just returned from right child 
       else if (curr.right == prev) { 
        if(!combineHeights(heights)) return false; 
        trail.pop(); //up to parent 
       } 
       //this came from a parent, first thing is to visit the left child, or right if no left 
       else { 
        if(curr.left != null) trail.push(curr.left); 
        else { 
         if (curr.right != null) { 
          heights.push(-1); //no left so when we combine this node left is 0 
          trail.push(curr.right); //since we never go left above logic does not go right, so we must here 
         } 
         else { //no children set height to 1 
          heights.push(0); 
          trail.pop(); //back to parent 
         } 
        } 
       } 

       prev = curr; 
      } 

      return true; 
     } 

     //pop both previous heights and make sure they are balanced, if not return false, if so return true and push the greater plus 1 
     private boolean combineHeights(Deque<Integer> heights) { 
      int rightHeight = heights.pop(); 
      int leftHeight = heights.pop(); 

      if(Math.abs(leftHeight - rightHeight) > 1) return false; 
      else heights.push(Math.max(leftHeight, rightHeight) + 1); 
      return true; 
     } 

Answer 2

书中的原题清楚没有提及树是二进制文件。我碰巧解决了同样的问题，但用Python编码。所以，这里是我的问题的迭代解决方案，在python中，一般树（节点的子节点存储在列表中）。

def is_balanced_nonrecursive(self): 
    stack = [self.root] 
    levels = [0] 
    current_min = sys.maxint 
    current_max = 0 
    current_level = 0 
    while len(stack) > 0: 
     n = stack.pop() 
     current_level = levels.pop() 
     for c in n.children: 
      stack.append(c) 
      levels.append(current_level + 1) 
     if len(n.children) == 0: 
      if current_level < current_min: 
       current_min = current_level 
      if current_level > current_max: 
       current_max = current_level 
    return current_max - current_min < 2 

这基本上是树的深度优先遍历。我们为各个级别保留一个单独的堆栈（列表levels）。如果我们看到任何叶节点，我们会相应地更新当前最小和当前最大值。该算法遍历整个树，最后如果最大和最小电平差异超过一个，那么该树不平衡。

可能有很多优化，例如检查循环内最小值和最大值的差值是否大于1，以及是否立即返回False。