二叉树的后序迭代遍历运行时间误差

Question

我在做一些 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; 

    }
};

请帮忙，谢谢！

Answer 1

当堆栈中只剩下一项时，您的代码在这里崩溃：

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) {

Answer 2

更正后的代码：附加检查是否是添加对空堆栈的检查

    #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

二叉树的后序迭代遍历运行时间误差

Postorder Iterative Traversal of Binary Tree Run Time Error

c++

iteration

traversal

postorder