二叉树深度优先搜索（非递归实现，迭代法）

目录

为什么可以用迭代法实现二叉树的前后中序遍历？

前序遍历

后序遍历

中序遍历

为什么可以用迭代法实现二叉树的前后中序遍历？

因为递归的实现本质是，每次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，这就是递归为什么可以返回上一层位置的原因。

所以我们可以用栈实现二叉树的前中后序遍历。

前序遍历

前序遍历的顺序是中左右，我们需要设置一个节点指针用来表示此时遍历的节点，先将该节点指针初始化为根节点，然后判断该节点指针是否为空指针，如果为空指针，则返回结果。如果不为空，那么先把根节点放入栈中，然后设置循环直到栈为空时循环结束。循环中将栈顶元素放入结果数组中，并弹出。然后先把该节点的右子节点放入栈中（如果该子节点不为空），把左子节点也放入栈中，然后进行下一次循环，这样就可保证下次循环先处理的是左子节点。

具体代码：

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

后序遍历

后序遍历的顺序是左右中。由于前序遍历的顺序是中左右，我们如果交换左右子节点入栈顺序，就可以实现左右子节点的遍历顺序的交换。所以将前序遍历的左右子节点压栈语句交换位置，可以实现中右左遍历顺序，然后对最后的结果数组进行翻转就可以实现左右中遍历顺序，即后序遍历。

具体代码：

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

中序遍历

在前序遍历中主要有两个操作：

处理：将元素放进result数组中

访问：遍历节点

前序遍历的顺序是中左右，先访问的是中间节点，要处理的元素也是中间节点，即要访问的元素和要处理的元素顺序是一致的。

中序遍历的顺序是左中右，先访问的是二叉树顶部的节点，然后一层层向下访问，直到到达树左边的最底部，然后才开始把节点数值放进结果数组中，即处理顺序和访问顺序不一致。

具体实现过程是：先设置循环直到栈为空结束循环，此时节点遍历完毕，返回结果数组。如果栈不为空，或者节点不为空则进入循环体内部，循环体内部需要先判断节点是否为空。如果不为空，就把该节点放入栈中，然后遍历下一个左节点（左）。如果节点为空，则将栈顶节点值放入结果数组中（中），然后弹出栈顶元素，同时遍历该节点的右子节点（右）。

具体代码：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(!st.empty() || cur!=nullptr) {
            if(cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }else {
                TreeNode* node = st.top();
                st.pop();
                result.push_back(node->val);
                cur = node->right;
            }
        }
        return result;
    }
};