используя стек, чтобы получить высоту BST - PullRequest
Новая
       5

используя стек, чтобы получить высоту BST

0 голосов
/ 14 сентября 2011

Я пытаюсь получить высоту 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;

}

1 Ответ

1 голос
/ 14 сентября 2011

Размер стека является неправильным значением глубины для некоторых узлов. Например. если текущий узел является правым потомком другого узла, стек не содержит этот другой узел (наш родитель). Для самого правого узла в дереве в стеке нет элементов.

Вам нужно будет правильно рассчитать глубину. В вашем случае вы можете подняться на большее количество уровней за один щелчок, поэтому вычитание одного не сработает, но если вы сохраните текущую глубину в стеке (и восстановите ее во время всплытия), она будет работать.

Чтобы сделать это, вы должны изменить определение стека, например, на 

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)

...