BSTの高さを非再帰的に見つけるか？

Question

これは高さを見つけるための再帰的な方法ですが、バイナリ検索ツリーに非常に多くのノードがあります。ツリーの高さを見つけて、個々のサブツリーに高さを割り当てたいと思います。だから再帰的なメソッドは、stackoverflowの例外をスローする、私はこれを非再帰的にスタックを使用せずに行うのですか？

private int FindHeight(TreeNode node) 
    { 
     if (node == null) 
     { 
      return -1; 
     } 
     else 
     { 
      node.Height = 1 + Math.Max(FindHeight(node.Left), FindHeight(node.Right)); 
      return node.Height; 
     } 
    } 

私は、トラバースのポストオーダーを使用しなければならないと思っていますが、スタックはありません。

Answer 1

私はこの方法をとることができました。正しい高さを返しますが、各ノードに深さが高さではなく、各ノードを割り当てます。

public void FindHeight() 
    { 
     int maxHeight = 0; 
     Queue<TreeNode> Q = new Queue<TreeNode>(); 
     TreeNode node; 
     Q.Enqueue(Root); 
     while (Q.Count != 0) 
     { 
      node = Q.Dequeue(); 
      int nodeHeight = node.Height; 
      if (node.Left != null) 
      { 
       node.Left.Height = nodeHeight + 1; 
       Q.Enqueue(node.Left); 
      } 
      if (node.Right != null) 
      { 
       node.Right.Height = nodeHeight + 1; 
       Q.Enqueue(node.Right); 
      } 
      if (nodeHeight > maxHeight) 
      { 
       maxHeight = nodeHeight; 
      } 

     } 
     Console.WriteLine(maxHeight); 
    }