二叉树中序遍历以栈的方式实现，不知哪里逻辑错误了？

Question

自己以栈的方式实现了一遍二叉树中序遍历，运行也没问题，但似乎是陷入了死循环，有没有高人点播下，代码如下：

#include<vector>
#include<iostream>
#include<stack>

using namespace std;

static int count = 0;
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x = 0):val(x),left(NULL),right(NULL){}
};
//中序遍历
vector<int> inorderTraveral(TreeNode *root){
    vector<int> res;
    stack<TreeNode *> s;
    TreeNode *pTree = new TreeNode();

    if(root != nullptr){
        s.push(root);
    }

    while(!s.empty()){
        pTree = s.top();

        if(pTree->left != nullptr){
            s.push(pTree->left);
            continue;
        }
        res.push_back(pTree->val);
        s.pop();

        if(pTree->right != nullptr) 
            s.push(pTree->right);

    }
    return res;
}
//递归遍历二叉树
void printTree(TreeNode *root){
    cout<<root->val<<" ";
    if(root->left != nullptr){
        printTree(root->left);
    }
    if(root->right != nullptr){
        printTree(root->right);
    }
}
//制造一个个数为k的完全二叉树
void makeTree(TreeNode* root,int k){
    TreeNode *tmpTree = new TreeNode(1);
    sranddev();
    tmpTree->val = rand()%100;

    if(count < k && root->left == nullptr){
        root->left = tmpTree;
        count++;
    }else if(count < k && root->right == nullptr){
        root->right = tmpTree;
        count++;
    }

    if(count < k){
        makeTree(root->left,k);
        makeTree(root->right,k);
    }
}

int main(){
    TreeNode *root = new TreeNode(10);

    int size;
    size = 10;

    TreeNode *root1,*root2;
    root1 = root2;

    makeTree(root,10);
    printTree(root);
    cout<<endl;

    vector<int> res;
    res = inorderTraveral(root);

    for(vector<int>::iterator it = res.begin(); it != res.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
}

输出陷入死循环，如下：

➜  leetcode  ./a.out 10 14 90 14 80 42 40 63 30 81 16 

谢谢你的提醒，后来参考了别人的代码，更改成功了，如下：

#include<iostream>
#include<stack>

using namespace std;
bool seqIsValid(const char*);
char seqRight(char);

bool seqIsValid(const char *str){
    stack<char> strStack;

    for(;*str != '\0';str++){
        if(!strStack.empty()){
            if(seqRight(strStack.top()) != *str){
                strStack.push(*str);
            }else{
                strStack.pop();
            }
        }else{
            strStack.push(*str);
        }
    }

    if(!strStack.empty()){
        return false;
    }
    return true;
}

char seqRight(char ch){
    switch(ch){
        case '[':
            return ']';
        case '{':
            return '}';
        case '(':
            return ')';
        default:
            return '\0';
    }
}

int main(){
    const char* test = "[{()}]";

    if(seqIsValid(test)){
        cout<<"seq is valid;"<<endl;
    }else{
        cout<<"is not valid"<<endl;
    }
}

Answer 1

vector<int> inorderTraveral(TreeNode *root){
    vector<int> res;
    stack<TreeNode *> s;
    TreeNode *pTree = new TreeNode(); //1

    if(root != nullptr){
        s.push(root);
    }

    while(!s.empty()){
        pTree = s.top();

        if(pTree->left != nullptr){ //2
            s.push(pTree->left);
            continue;
        }
        res.push_back(pTree->val);
        s.pop();

        if(pTree->right != nullptr) 
            s.push(pTree->right);

    }
    return res;
}

1、为什么这里要new TreeNode()？
2、你想想，遍历到第一个节点后，你将这个节点从栈里pop()了，然后你又拿了个top()指针，也就是这个节点的parent，然后访问left，这不就是你刚才访问的第一个节点么？这里就死循环了！

           root
          /
        a1
       /
     a2
    /
  null

一开始建立的栈是这样：

a2
a1

当你运行到：

    res.push_back(pTree->val);
    s.pop();

时，栈是这样：

a1

这时top()拿出来的就是a1，然后if(pTree->left != nullptr)，悲剧了:)