スタックを使用してBSTの高さを取得する

Question

スタックを使用してBSTの高さを取得しようとしています。私はプリオーダーを使用して、スタックの最大サイズを調べるべきだと言われました。しかし、これは動作していないようです。私が間違っていることのアイデア。

int PBT::maxDepth() { 
if (!root) { 
    return -1; 
} 
int depth=0; 
stack<TreeNode *>s; 
TreeNode * nodePtr=root; 
for (; ;) {   
    while (nodePtr) { 
     s.push(nodePtr); 
     if (s.size() > depth) 
      depth = s.size(); 
     nodePtr=nodePtr->left; 
    }if (s.empty()) { 
     break; 
    } 
    nodePtr=s.top(); 
    s.pop(); 
    nodePtr=nodePtr->right; 
} 
return depth; 

}

Answer 1

スタックサイズは、いくつかのノードに対する深さの誤った値です。例えば。現在のノードが他のノードの右の子である場合、スタックはこの他のノード（私たちの親）を含みません。ツリーの最右ノードの場合、スタックにはアイテムはありません。

深度を正しく計算する必要があります。あなたのケースでは、あなたは1つのポップでさらにレベルを上げるかもしれないので、1つを引くことはできませんが、あなたの現在の深さをスタックに保存して（そしてポップ中に復元すると）うまくいくでしょう。

これを行うには、スタック定義をたとえば次のように変更する必要があります。

stack<pair<TreeNode*, unsigned> > stack; 

とし、変数current_depthを追加します。

各 "nodePtr=nodeptr->left/right"については、current_depthを増分します。私があなただったら、私は簡単なテストケースを見つけるだろう