스택을 사용하여 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

(노드 포인터가 .first에 분명히)

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

으로 밀어 당신이 팝업 전에

current_depth = s.top().second;

와 current_depth을 복원하는 작동하지 않으며 디버거의 코드를 단계별로 실행하여 어떤 일이 일어나고 있는지 반드시 생각해야합니다. – NPE

여러 경우에서 선주문에 문제가 있는지 확인하려고했습니다. 선주문이 작동하는 것을 압니다. – Aaron

그래서 어떤 식으로 코드가 작동하지 않습니까? 실제 나무와 예상 나무 나무가 작동하지 않는 나무의 예를 들어 줄 수 있습니까? – NPE

스택의 크기는 일부 노드에 대한 깊이의 잘못된 값입니다. 예 : 현재 노드가 다른 노드의 오른쪽 하위 노드이면 스택에이 다른 노드 (상위 노드)가 포함되지 않습니다. 트리의 가장 오른쪽 노드의 경우 스택에 항목이 없습니다.

깊이를 올바르게 계산해야합니다. 당신의 경우, 하나의 팝에서 더 많은 레벨을 올릴 수 있습니다. 따라서 하나를 빼면 효과가 없지만, 현재의 깊이를 스택에 저장하면 (그리고 터지는 동안 복원) 작동하게됩니다.

이렇게하려면 스택 정의를 예를 들어로 변경해야합니다.

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

그리고 변수 current_depth을 추가하십시오.

각 "nodePtr=nodeptr->left/right"에 대해 current_depth이 증가합니다. 내가 당신이라면, 간단한 테스트 케이스를 찾을 것

출처

2011-09-14 16:04:16 jpalecek

'depth'는 지금까지 발견 된 최대 깊이입니다. 재설정하는 것은 의미가 없습니다. 내 말은, – interjay

. 나는 나의 대답을 편집했다. – jpalecek

나는 스택의 값을 튀기기 전에 올바른 자식에 대한 변수에 추가하지 않는 문제가 여전히 발생했습니다. – Aaron

스택을 사용하여 BST 높이 얻기

답변

관련 문제