最近写试卷的时候老是遇到卡递归写法的题目, 搞得我好难受, 特意来学下非递归写法;

树的结构：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

前序遍历:

/*
    使用递归时电脑会自动调用系统栈, 因此递归回溯时不用额外操作; 
    使用非递归的写法则需要用栈手动记录回溯的节点;

    前序遍历顺序为: 根-左-右; 
    因此每执行到"根"时, 都要将节点保存到栈中作为回溯的节点;
*/
vector<int> preTraversal(TreeNode* root)
{
    vector<int> res;
    stack<TreeNode*> stk;
    TreeNode *p = root;

    while(p || stk.size())
    {
        while(p) 
        {
            res.push_back(p->val);
            stk.push(p);                    // 每个"根"节点都要入栈, 方便回溯;
            p = p->left;                    // 前序先遍历左子树, 因此要一直向左遍历;
        }
        p = stk.top()->right;               // 向左走不了时才回溯到上一个节点的右子树;
        stk.pop();
    }

    return res;
}

中序遍历

/*
    中序遍历的顺序是:左-根-右;
    中序遍历优先往左走, 但后面还要回到根节点, 因此也要入栈每一个遍历到的节点; 
*/
vector<int> inorderTraversal(TreeNode* root)
{
    vector<int> res;
    stack<TreeNode*> stk;
    TreeNode *p = root;

    while(p || stk.size())
    {
        while(p)
        {
            stk.push(p);                    
            p = p->left;                    // 一直往左遍历, 入栈每一个节点; 
        }
        p = stk.top();                      // 向左走到头后, 回到栈记录的上一个根节点;
        stk.pop();                          // 根遍历完了就可以出栈了;
        res.push_back(p->val);
        p = p->right;                       // 再向右走;
    }

    return res;
}

后序遍历非递归

/*
    后序遍历的访问顺序是: 左-右-根;
    我们先经过根节点，但是我们不会去访问它，而是会选择先访问它的右节点;
    这种情况下，我们会将根节点留在栈中不弹出，等到需要访问它的时候再出;

    只有两种情况能访问根节点:
    1. 当前经过节点是叶子节点;
    2. 根节点的右节点被遍历输出过;

    * 参考自: https://zhuanlan.zhihu.com/p/80578741
*/
vector<int> postorderTraversal(TreeNode* root)
{
    vector<int> res;
    stack<TreeNode*> stk;
    TreeNode *p = root, *last;                      // last用于记录上一个输出的节点;

    while(p || stk.size())
    {
        while(p) 
        {
            stk.push(p);
            p = p->left;
        }

        if(stk.size())
        {
            TreeNode *t = stk.top();                // t记录的是存储在栈顶的根节点; 
            if(!t->right || last == t->right)       // 判断根节点的访问条件;
            {
                res.push_back(t->val);
                stk.pop();                          // 根节点访问后就出栈, 并更新last节点; 
                last = t;
            }
            else p = t->right;                      // 根节点不能访问的话就去遍历右子树;
        }
    }

    return res;
}

Morris遍历

在写试卷的时候, 还遇到一种神奇的非递归遍历方式;
相较于上面使用栈的迭代形式, 这种遍历可以做到空间消耗为O(1), 时间仍为O(n);
后查阅得知, 这类遍历名叫Morris遍历;

/*
    Morris遍历利用了叶子结点的空指针从而达到O(1)的空间消耗; (有点像线索二叉树)

    以前序遍历为例:
        前序遍历的顺序为: 左-根-右;
        Morris遍历先让左子树中最后一个被遍历到的叶节点指向根;
        这样在对左子树做前序遍历的时候, 一旦遍历到了根节点就表明左子树遍历完毕, 从而开始遍历右子树;

    * 代码参考自: https://www.acwing.com/blog/content/414/
*/
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode* p = root;

    while (p != NULL)
    {
        if(p->left == NULL)                     // 左子树为空则直接遍历右子树;
        {
            res.push_back(p->val);
            p = p->right;
        }
        else
        {
            TreeNode* t = p->left;
            while(t->right != NULL && t->right != p) t = t->right;          // 找左子树前序遍历的最后一个节点;
                                                                            // 也就是左子树的最右边的节点;
            if(t->right == NULL)                // 让左子树先序遍历的最后一个节点指向根, 并开始遍历左子树;
            {
                t->right = p;
                res.push_back(p->val);
                p = p->left;
            }
            else                                // 如果左子树遍历回到了根, 就说明左子树遍历完毕, 转而开始遍历右子树;
            {
                t->right = NULL;
                p = p->right;
            }
        }
    }
    return res;
}