使用堆棧來獲得BST的高度

我想要使用堆棧來獲得BST的高度。我被告知我應該使用預定義和度量來查找堆棧的最大尺寸。但是，這似乎並不奏效。任何想法我做錯了什麼。使用堆棧來獲得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;

}

來源

2011-09-14 Aaron

如果我是你，我會找到一個簡單的測試用例在調試器中無法正常工作並遍歷代碼，以查看是否發生了什麼是您認爲應該發生的事情。 – NPE

我已經嘗試了多種情況來查看預訂是否有問題。我知道前序奏效。 – Aaron

那麼你的代碼不工作的方式是什麼？你能舉一個簡單的樹的例子，它不起作用，以及實際與預期的產出？ – NPE

堆棧大小是深度爲一些節點的不正確的值。例如。如果當前節點是其他節點的右側子節點，則堆棧不包含這個其他節點（我們的父節點）。對於樹中最右邊的節點，堆棧將沒有項目。

您必須正確計算深度。在你的情況下，你可能會在一個彈出窗口中增加更多的級別，所以減去一個彈出窗口不會奏效，但是如果你將當前的深度保存到堆棧（並在彈出時恢復它），它就可以工作。

要做到這一點，你應該改變你的堆棧定義爲例如。

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

並添加變量current_depth。

對於每個「nodePtr=nodeptr->left/right」，您增加current_depth。與

s.push(make_pair(nodeptr, current_depth));

推，你去之前，恢復current_depth與

current_depth = s.top().second;

（節點指針顯然是.first）

來源

2011-09-14 16:04:16 jpalecek

深度是迄今爲止發現的最大深度。重置它沒有任何意義。 – interjay

我明白了。我編輯了我的答案。 – jpalecek

我試過，我仍然有問題，它沒有添加到正確的孩子的變量之前它彈出一個值的堆棧 – Aaron

使用堆棧來獲得BST的高度

回答

相關問題