二叉树前序、中序、后序、层序遍历的非递归实现。

前序遍历：

LeetCode链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

实现思路：

　　使用栈来模拟递归遍历操作。注意子节点的入栈顺序是 先右后左 ，因为栈后进先出（LIFO）的特性，左子节点将晚于右子节点被取出，这正符合了前序遍历 " 根->左->右 "的遍历顺序。

代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     vector<int> preorderTraversal(TreeNode* root) {
15         if(!root) return {};    //空树直接返回空的数组
16         vector<int> result;        //用于存储遍历结果的向量
17         stack stk;   //存储树节点指针变量的栈
18         stk.push(root);     //将根节点压入栈中
19         
20         while( !stk.empty() ) { //当栈为空时，退出循环  
21             TreeNode* node = stk.top();     //使用临时变量保存栈顶结点
22             stk.pop();      //将栈顶节点弹出栈
23             result.emplace_back(node->val);    //将节点的值插入到结果向量中
24             if(node->right) stk.push(node->right);  //右子树非空，则压入栈中
25             if(node->left) stk.push(node->left);    //左子树非空，则压入栈中
26         }
27 
28         return ans;
29     }
30 };

后序遍历：

LeetCode链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

实现思路：

　　使用栈来模拟递归遍历的操作，同前序遍历的操作十分类似。但是要注意，后序遍历左右子节点的入栈顺序为 先左后右 ，这样遍历的顺序实际上是 “ 根->右->左 ”，与后序遍历的 " 左->右->根 "恰好完全相反，因此，将所有节点都遍历完成后，切记要将遍历结果result反转。下面的代码中，使用了使用STL algorithm头文件中的reverse方法来反转遍历结果向量result。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        stack stk;
        vector<int> result;
        stk.push(root);
        while(!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            result.emplace_back(node->val);
            if(node->left) {
                stk.push(node->left);
            }
            if(node->right) {
                stk.push(node->right);
            }
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

中序遍历：

LeetCode链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

实现思路：

　　使用栈来模拟递归遍历操作。同前序遍历、中序遍历的节点入栈、出栈顺序有很大的区别，需要仔细体会入栈、出栈操作的过程。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> result;
        stack stk;
        while(root || !stk.empty()) {
            while(root) {
                stk.push(root);
                root = root->left;
            }
            if(!stk.empty()) {
                TreeNode* node = stk.top();
                stk.pop();
                result.emplace_back(node->val);
                root = node->right;
            }
        }
        return result;
    }
};

层序遍历：

LeetCode链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

实现思路：

　　使用队列来实现层序遍历操作。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vectorint>> levelOrder(TreeNode* root) {
        if(!root) return{};
        vector< vector<int> > result;
        queue que;
        que.push(root);
        while(!que.empty()) {
            int queSize = que.size();
            vector<int> temp;
            for(int i = 0; i < queSize; i++) {
                TreeNode* node = que.front();
                que.pop();
                temp.emplace_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.emplace_back(temp);
        }
        return result; 
    }
};