ツリーがバランスしているかどうかを調べる反復的な解決策

Question

誰かが解決策を投稿しましたが、うまくいかないことがわかりました。私はそこに投稿しましたが、

質問は、「コードのインタビューをクラッキング」であり、それは最初のツリーの質問で、他の提案を行い気軽に（あるいは私が間違っていることを証明！）

Answer 1

ここで重要なのは、トラックを保つことが困難であるということです1つのスタックで最終的なパスとその高さの

私がやったことは、左右の子供の高さをスタックに押し込んで、互いの間にあるかどうかをチェックし、最大に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つ以上異なる場合、ツリーは平衡しません。

ループ内でminとmaxの差が2つ以上あるかどうかを確認するなど、多くの最適化が可能です。その場合はすぐにFalseを返します。