非递归式遍历二叉树

主要可以分为两类：
第一类——中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> rec;
        if(root==NULL)
          return rec;
        stack<TreeNode*> s;
        while(!s.empty()||root!=NULL)
        {        
            while(root!=NULL)  //把左子树全部压入栈中
            {
                s.push(root);
                root = root->left;
            }
            root = s.top();
            rec.push_back(root->val);
            s.pop();
            root = root->right;
        }
        return rec;
    }
};

第二类——前序遍历，后序遍历，水平遍历

前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> rec;
        if(root==NULL)
          return rec;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            root = s.top();
            rec.push_back(root->val);
            s.pop();
            if(root->right)
              s.push(root->right);
            if(root->left)
              s.push(root->left);
        }
        return rec;
    }
};

后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> rec;
        if(root==NULL)
          return rec;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            root = s.top();
            rec.push_back(root->val);
            s.pop();
            if(root->left)
              s.push(root->left);
            if(root->right)
              s.push(root->right);
        }
        reverse(rec.begin(),rec.end());
        return rec;
    }
};

水平遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> rec;
        if(root==NULL)
           return rec;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> temp;
            int height = q.size(); //某行的节点总数
            int i = 0;
            while(i<height)
            {
                TreeNode* p = q.front();
                temp.push_back(p->val);
                q.pop();
                if(p->left)
                  q.push(p->left);
                if(p->right)
                  q.push(p->right);
                i++;
            }
            rec.push_back(temp);
        }
        return rec;
    }
};

之字形遍历

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> rec;
        if(root==NULL)
          return rec;
        queue<TreeNode*> q;
        q.push(root);
        int count = 0;
        while(!q.empty())
        {
            vector<int> temp;           
            int height = q.size();  //某行的节点总数
            int i = 0;
            while(i<height)
            {
                TreeNode* p = q.front();
                temp.push_back(p->val);
                q.pop();
                if(p->left)
                  q.push(p->left);
                if(p->right)
                  q.push(p->right);
                i++;
            }
            if(count%2!=0)
              reverse(temp.begin(),temp.end());
            count++;
            rec.push_back(temp);
        }
        return rec;
    }
};