二叉树的迭代法遍历、统一迭代法遍历

144. 二叉树的前序遍历

采用迭代的方式进行实现 。

递归时使用栈存储临时变量和参数，因此也可以使用栈来实现二叉树的遍历。

前序遍历是中左右，因而入栈顺序应该是先右后左，出栈即为左右。

每次取出栈顶元素，放入结果中，再将栈顶元素的右、左分别压栈即可。

代码实现：

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vectorresult;
        stack s;
        if(root == NULL)
            return result;
        s.push(root);
        while(!s.empty()){
            TreeNode* cur = s.top();
            s.pop();
            result.push_back(cur->val);
            if (cur->right)//空节点不入栈
                s.push(cur->right);
            if (cur->left)
                s.push(cur->left);
        }
        return result;
    }
};

94. 二叉树的中序遍历

可能一上来想按照和前序遍历一样的解法来写，但是此处并不行。

前面的迭代过程中，其实有两个 *** 作：

（1）处理节点：将元素push_back放入result中

（2）访问元素

在前序遍历时要访问的元素和要处理的元素顺序是一致的，都是中间节点。

但是中序遍历并不一致，中序遍历先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

先访问后处理，因此此时使用一个栈存储将要处理的元素，使用一个指针进行访问。

首先访问至最底层（指针指向NULL），然后出栈，处理元素，再访问其右侧节点。

代码实现：

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vectorresult;
        stackst;
        if(root == NULL)
            return result;
        TreeNode* p = root;
        while(p != NULL || !st.empty()){
            if (p == NULL){//p访问至最底层，再进行处理(最底层时没有左节点，只剩下了中右)
                p = st.top();
                st.pop();
                result.push_back(p->val);//中
                p = p->right;//右
                    
            }
            else{
                st.push(p);
                p = p->left;
            }
        }
        return result;
    }
};

145. 二叉树的后序遍历

二叉树后序遍历的顺序为左右中，前序遍历为中左右，只需要将前序遍历修改为中右左，再对结果进行反转即为后序遍历的结果左右中。

 

代码实现：

class Solution {
public:
    
    vector postorderTraversal(TreeNode* root) {
        vector result;
        stackst;
        if (root == NULL)
            return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* p = st.top();
            st.pop();
            result.push_back(p->val);//中
            if (p->left)//先压左再压右，出栈是为右左
                st.push(p->left);
            if (p->right)
                st.push(p->right);
        }
        reverse(result.begin(), result.end());//中右左反过来即为中左右
        return result;
    }
};

二叉树的统一迭代法：

前面前序遍历和后序遍历稍加修改即可实现，但是中序遍历由于访问和处理的顺序不一致，无法稍加修改实现。

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记，就是在要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

 这种方法也可以叫做标记法。

统一迭代中序遍历如下：（代码来自carl）

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector result;
        stack st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点d出，避免重复 *** 作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。



                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点d出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

 前序遍历时只需将中间部分改为：

if (node->right) st.push(node->right);  // 右
if (node->left) st.push(node->left);    // 左
st.push(node);                          // 中
st.push(NULL);

后序遍历时：

st.push(node);                          // 中
st.push(NULL);

if (node->right) st.push(node->right);  // 右
if (node->left) st.push(node->left);    // 左