二叉树的迭代遍历

1. 层次遍历

层次遍历是广度优先遍历，即先遍历二叉树的每一层节点，再向下继续遍历每一个节点的子节点。基本思想是，当同层节点都遍历后，此时同层节点的子节点进行下一轮遍历，不难想到，我们应该使用队列来实现这一想法。因为队列先进先出的特性，使得同层的节点必定相邻，我们只需要将同层每个节点放入队列后，在它们按序出列时放入子节点即可。
下面是层序遍历的代码模板，事实上，这份模板可以解决很多类似于层序遍历的问题，只需要修改很少的部分即可：

class Sulution{
    public:
        vector<vector<int>> levelOrder(TreeNode* root){
            queue<TreeNode*> que;
            vector<vector<int>> result;
            if(root == NULL)return result;
            que.push(root);
            while(!que.empty()){
                int size = que.size();
                vector<int> vec;
                for(int i = 0; i < size; i++){
                    TreeNode* cur = que.front();
                    que.pop();
                    vec.push_back(cur->val);
                    if(cur->left)que.push(cur->left);
                    if(cur->right)que.push(cur->right);
                }
                result.push_back(vec);
            }
            return result;
        }
}

这样每一层的节点都保存至一个vector内，每一层迭代结束后，将相应的vector保存到result中。

2. 前序遍历

在上一期实现递归深度优先遍历时，其实关键就是将每一次递归调用的函数局部变量、参数值和返回地址压入调用栈中，然后调用返回后，从栈顶弹出上一次递归的各项参数，这就是递归能返回最终结果的原理。那么我们当然可以手动使用stack来实现模拟这一过程。

栈（stack）空间先入后出，对于前序遍历中左右的结果，首先将根节点放入栈中，然后弹出栈顶元素，再放入右孩子，最后放入左孩子，这样出栈的顺序才正确。代码如下：

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

3. 后序遍历

前序遍历是中左右的顺序，后序遍历是左右中的顺序。而恰恰我们可以调整前序遍历放入子节点的左右顺序来产生中右左的序列（此时先放入左子节点，后放入右子节点），然后将这个序列逆序即可得到左右中的顺序。代码只需要在前序的基础上修改少部分即可：

class Solution{
    public:
        vector<int> preOrder(TreeNode* root){
            stack<TreeNode*> stk;
            vector<int> result;
            if(root == NULL)return result;
            stk.push(root);
            while(!stk.empty()){
                TreeNode* cur = stk.top();//中
                stk.pop();
                result.push_back(cur->val);
                if(cur->left)stk.push(cur->left);//先放入左
                if(cur->right)stk.push(cur->right);//后放入右
            }
            reverse(result.begin(), result.end());//逆序
            return result;
        }
}

4. 中序遍历

中序遍历的顺序是左中右，此时如果我们还按照上述的方法进行中序遍历就会发现，当访问到左节点时，紧跟的“中”是其父节点，这就造成了不便性。这里我们使用一个指针来控制访问元素，栈则用来处理节点上的元素。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while(cur != NULL || !stk.empty()){
            if(cur != NULL){//指针访问节点，访问到最左下的起始元素
                stk.push(cur);
                cur = cur->left;//左
            }else{//当前节点为空时，将栈顶元素拿出来
                cur = stk.top();
                stk.pop();
                result.push_back(cur->val);//中节点
                cur = cur->right;//访问右子节点
            }
        }
        return result;
    }
};

中序遍历需要仔细思考一下其原理，最好是在纸上测试一遍，这里蕴含的其实是“回溯”的知识，在之后的题解中，也会涉及到二叉树+回溯的题目，即在当前元素遍历后，如何再回到父节点再向另一个方向遍历。需要仔细体会。