迭代解決方案尋找樹是否平衡

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。