Постеральный итерационный обход ошибки времени выполнения двоичного дерева
Я занимался вопросами LeetCode (впервые в LeetCode) и написал решение для итеративного обхода двоичного дерева. Я использовал стек, и я считаю, что моя логика работает, но LeetCode дает мне ошибку во время выполнения. Как я могу это исправить?
Вот мой код:
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
TreeNode* temp = root;
vector<int> v;
stack<TreeNode*> s;
if (temp == NULL)
return v;
while (true){
while (temp != NULL){
if (temp->right)
s.push(temp->right);
s.push(temp);
temp = temp->left;
}
if (s.empty())
break;
temp = s.top();
s.pop();
if (s.top() == temp->right){
s.pop();
s.push(temp);
temp = temp->right;
}else{
v.push_back(temp->val);
temp = NULL;
}
}
return v;
}
};
Пожалуйста, помогите, спасибо!
Решение
Ваш код падает здесь, когда в стеке остался только один элемент:
temp = s.top(); // remove the last item from the stack
s.pop(); // empty the stack
if (s.top() == temp->right){ // attempt to access the top of the stack.. boom!
Исправление состоит в том, чтобы проверить пустой стек перед проверкой top:
if (!s.empty() && s.top() == temp->right) {
Другие решения
Исправленный код:
Дополнительная проверка, если это добавить проверку пустого стека
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
class TreeNode{public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(){
left=right=NULL;
}
TreeNode(int data){
val=data;
}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root)
{
TreeNode* temp = root;
vector<int> v;
stack<TreeNode*> s;
if (temp == NULL)
return v;
while (true){
while (temp != NULL){
if (temp->right)
s.push(temp->right);
s.push(temp);
temp = temp->left;
}
if (s.empty())
break;
temp = s.top();
s.pop();
if (!s.empty() && s.top() == temp->right) {
s.pop();
s.push(temp);
temp = temp->right;
}else{
v.push_back(temp->val);
temp = NULL;
}
}
return v;
}
};
int main(){
TreeNode* root = NULL;
root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
Solution obj;
vector<int >v;
v =obj.postorderTraversal(root);
for(auto i=v.begin();i!=v.end();++i)
cout<<*i;
}
Выход:
4526731