stack实现二叉树的先序与中序遍历

（1）利用stack实现二叉树的先序与中序遍历，程序基本差不多，访问的顺序不同，后续遍历就要麻烦许多。

中序遍历：

#include<stack>
#include<vector>
using namespace std;
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Solution{
public:
    vector<int> InOrderTravel(TreeNode * root){
        stack<TreeNode*> s;
        vector<int> ret;
        TreeNode *p=root;
        while(p!=NULL||s.size()!=0){
            if(p!=NULL){
                s.push(p);
                p=p->left;
            }
            else{
                p=s.top();
                s.pop();
                ret.push_back(p->val);
            }
        }
        return ret;
     }
}

先序遍历：

class Solution{
public:
    vector<int> PreOrderTravel(TreeNode * root){
        vector<int> ret;
        stack<TreeNode*> s;
        TreeNode *p=root;
        while(s.size()!=0||p!=NULL){
            if(p!=NULL){
                ret.push_back(p->val);
                s.push(p);
                p=p->left;
            }
            else{
                p=s.top();
                p=p->right;
                s.pop();
            }
        }
        return ret;
    }
}