非递归（迭代）遍历二叉树

前言

在树结构中我们经常使用递归算法，但是递归本身的特质会带来很多疑难痛点，比如递归过深导致爆栈，或者是逻辑复杂...

本文将以树的前序遍历为例，浅析迭代算法如何模拟递归过程。

思路

我们先来看看这个算法的具体思想。
在递归中一般是：左子树 - 根 - 右子树

但是在非递归中：左斜列 - 右节点 - 右节点的左斜列

在行进中是类似于这样的感觉，最左一斜列为基底，通过条件向右一步，然后向左走到底，然后再向右......

红圈为空黑圈有值

那么区别在哪呢？
迭代算法走到空节点时，可以直接跳到父节点的右节点。

代码示例

这里给出力扣的一道例题

/**
 * 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> preorderTraversal(TreeNode* root) 
    {
        //用栈st存最左斜列的节点
        stack<TreeNode*> st;
        //顺序表vi存输出的val值
        vector<int> vi;
        
        //定义cur用以遍历
        TreeNode* cur = root;

        //开始迭代，如果cur或者st不为空，那么循环继续
        while(!st.empty() || cur)
        {
            //一直向左走，边走边记录节点和值
            while(cur)
            {
                st.push(cur);
                vi.push_back(cur->val);
                cur = cur->left;
            }

            //取cur的父节点
            TreeNode* top = st.top();
            //解决每一个父节点，标志着这个父节点的左树已经遍历过了
            st.pop();

            //向左走到尽头后，向右一步
            cur = top->right;
        }

        //输出答案
        return vi;
    }
};