本文创建于 231128，于 250925 从笔记中进行迁移。

二叉树的遍历问题非常经典，用递归方式实现非常简单。但当递归的程序栈交由自己管理时，事情还会简单吗？

本文主要内容：

树遍历的基本概念与特点
层序遍历方式
前、中、后序遍历的递归方式
前、中、后序遍历的常规迭代方式
前、中、后序遍历的模拟程序栈方式
前、后序互转技巧
Morris 算法

本文题目难度标识：🟩简单，🟨中等，🟥困难。

基本概念与特点

系统地访问有序树的每个结点，使得对每个结点恰好访问一次，进行数据存取的过程称为有序树遍历算法。

二叉树的遍历分为：

先序遍历（前序遍历）：访问次序为根、左子树、右子树
中序遍历：访问次序为左子树、根、右子树
后序遍历：访问次序为左子树、右子树、根
层次遍历

所谓「序」即指根节点何时被访问。

由遍历序列构造二叉树：

唯一确定一棵二叉树（具体算法实现可看后文）：
- 先序序列 + 中序序列
- 后序序列 + 中序序列
- 层序序列 + 中序序列
无法唯一确定一棵二叉树：
- 先序序列 + 后序序列。但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为 XY、后序序列为 YX 时，则 X 为 Y 的祖先。

在任意一棵二叉树的前序序列和后序序列中，各叶子之间相对次序关系都相同。叶子结点位于左右两个分支上，先序和后序的遍历属性均是左子树在右子树之前（相对次序一定相同），和二叉树的样式无关。

层序遍历

🟨 102. 二叉树的层序遍历 - 力扣（LeetCode）

自下而上、从右到左的层次遍历算法：利用原有的层次遍历算法，出队的同时将各个结点的指针入栈，在所有结点入栈后再从栈顶开始依次访问。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)return new ArrayList<>();
        Deque<TreeNode> q = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        q.offer(root);
        List<Integer> layer;
        while(q.size()>0){
            int now = q.size(); // 确定当前层次的层数
            layer = new ArrayList<>();
            for(int i=0;i<now;i++){
                TreeNode node = q.poll();
                layer.add(node.val);
                if(node.left!=null){
                    q.offer(node.left);
                }
                if(node.right!=null){
                    q.offer(node.right);
                }
            }
            ans.add(layer);
        }
        return ans;
    }
}

复杂度分析：记树上所有节点的个数为 n。

时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 $O(n)$ 。
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 $O(n)$ 。

层序遍历特点：结点是一层一层加的。利用这个特点可以知道每一层的高度。比如维护 Map 数组记录每个结点的深度。

如果不需要记录高度，需要在每层结点处理之间加入间隔，可以维护变量，在装入队列时记录下一层结点的个数。但实际上，遍历每层前队列的大小就是最好的间隔，如上面代码中的 int now = q.size();。

前、中、后序遍历的递归方法

🟩 144. 二叉树的前序遍历 - 力扣（LeetCode）

🟩 94. 二叉树的中序遍历 - 力扣（LeetCode）

🟩 145. 二叉树的后序遍历 - 力扣（LeetCode）

void Track(BiTree *T){
	if(T==NULL)return;
	// 前序遍历visit于此
	Track(T->left);
	// 中序遍历visit于此
	Track(T->right);
	// 后序遍历visit于此
}

递归工作栈栈深恰好为树的深度。在最坏情况下，二叉树是有 n 个结点，深度为 n 的单支树，遍历算法的空间复杂度为 $O(n)$ 。

别看上面的题目难度标识为简单，那只是对于递归方式实现而言。用迭代方式去实现可不一定简单。

前、中、后序遍历迭代方法

前、中、后序遍历常规迭代方法

前序遍历非递归：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode w = root;
        while(w!=null || stack.size()>0){
            while(w!=null){
                ans.add(w.val); // 变动点
                stack.push(w);
                w=w.left;
            }
            w = stack.pop();
            w = w.right;
        }
        return ans;
    }
}

中序遍历非递归：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode w = root;
        while(w!=null || stack.size()>0){
            while(w!=null){
                stack.push(w);
                w=w.left;
            }
            w = stack.pop();
            ans.add(w.val); // 变动点
            w = w.right;
        }
        return ans;
    }
}

前序遍历和中序遍历实现的不同之处，只在于访问环节的位置不同。

后续遍历非递归：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode w = root;
        TreeNode prev = null; // 维护上次 visit 过的结点
        while(w!=null || stack.size()>0){
            while(w!=null){
                stack.push(w);
                w=w.left;
            }
            w = stack.peek(); // 打算 visit 此中结点
            if(w.right == null || w.right == prev){
                // 右边没有可以遍历的了
                ans.add(w.val);
                prev = stack.pop();
                w = null; // 目的是跳过前面的 while
            }else{
                // 右边可以遍历
                w = w.right;
            }
        }
        return ans;
    }
}

后序遍历引入指针 prev，记录上一次遍历过的结点。这个非递归后序遍历特点是：栈中所有元素的结点均为该结点的祖先。

后序遍历的方法是不是好像和前面的前序遍历、中序遍历的方法差别很大？不好记忆的话，可以使用文章后面提到的「根右左逆序」技巧。

前、中、后序遍历的模拟栈方法（颜色标记法）

在上面的迭代方法中，看着各种嵌套循环可能会非常烧脑，导致「一看就会、一用就废」。不同遍历顺序的循环结构差异较大，增加记忆负担。LeetCode 中的网友 henry 介绍了一种简单的迭代方法，不同遍历的循环结构几乎一致，递归方式一样好懂。下面我将对其思想进行优化和解析。

核心思想：

为每个结点添加 boolean 类型的标记 isUnfold，表示一个结点是否进行「展开」过。新结点默认为「未展开」状态。
不断获取栈中元素：
- 如果弹出的结点未展开。那么将弹出的结点自身标记为展开，然后按一定的顺序将其左右结点和自身入栈。
- 如果弹出的结点已经展开。那么就 visit 该结点（加入答案数组），进入下一轮迭代。

下面演示的是前序遍历的代码。

由于 henry 将这种做法成为「颜色标记法」，这里我就借「颜色」这个概念，新定义带标记的结点。颜色结点的包装代码如下：

class ColorNode{
    TreeNode node;
    boolean isUnfold; // 颜色标记
    ColorNode(TreeNode node){
        this.node = node;
    }
    // 展开结点
    public ColorNode unFold(){
        this.isUnfold = true;
        return this;
    }
}

前序遍历：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<ColorNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        if(root==null)return ans;
        ColorNode w = new ColorNode(root);
        stack.push(w);
        while(stack.size()>0){
            w = stack.pop();
            if(w.isUnfold){
                ans.add(w.node.val);
                continue;
            }
            // 右 - 左 - 中 依次入栈
            if(w.node.right!=null)stack.push(new ColorNode(w.node.right));
            if(w.node.left!=null)stack.push(new ColorNode(w.node.left));
            stack.push(w.unFold());
        }
        return ans;
    }
}

中序遍历：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<ColorNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        if(root==null)return ans;
        ColorNode w = new ColorNode(root);
        stack.push(w);
        while(stack.size()>0){
            w = stack.pop();
            if(w.isUnfold){
                ans.add(w.node.val);
                continue;
            }
            // 右 - 中 - 左 依次入栈
            if(w.node.right!=null)stack.push(new ColorNode(w.node.right));
            stack.push(w.unFold());
            if(w.node.left!=null)stack.push(new ColorNode(w.node.left));
        }
        return ans;
    }
}

后序遍历：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<ColorNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        if(root==null)return ans;
        ColorNode w = new ColorNode(root);
        stack.push(w);
        while(stack.size()>0){
            w = stack.pop();
            if(w.isUnfold){
                ans.add(w.node.val);
                continue;
            }
            // 中 - 右 - 左 依次入栈
            stack.push(w.unFold());
            if(w.node.right!=null)stack.push(new ColorNode(w.node.right));
            if(w.node.left!=null)stack.push(new ColorNode(w.node.left));
        }
        return ans;
    }
}

「颜色标记法」入栈方式特别像递归，其的原理在于我们通过代码模拟了递归的过程，只不过递归时是程序中的方法调用栈，这里是用代码模拟这个栈。

至此，也许你已经快速掌握了更加容易记得非递归遍历二叉树的方式。注意到，先序遍历的写法中还可以存在优化的地方。先序遍历中「右 - 左 - 中」依次入栈后，下一轮迭代中，解折叠后的「中」会首先弹出来并加入答案中，看起来上下两次迭代中，对于「中」结点的入栈和出栈可以在一次迭代中完成。

在一次迭代中，我们可以把解折叠后的「中」结点直接加入答案数组不再压栈。这样的话，isUnFold 的结点状态标记就没意义了，我们可以把颜色结点退化为基本的树结点。

先序遍历简化写法：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode w = root;
        if(w!=null)stack.push(w);
        while(stack.size()>0){
            w = stack.pop();
            ans.add(w.val);
            if(w.right!=null)stack.push(w.right);
            // ans.add(w.val); // 也可以写在这，反正不入栈
            if(w.left!=null)stack.push(w.left);
            // ans.add(w.val); // 也可以写在这，反正不入栈
        }
        return ans;
    }
}

翻转前序遍历结果可得到后序遍历结果

前序遍历中遍历结点的顺序为：访问根 - 遍历左子树 - 遍历右子树。访问根后，我们往往会将子树进行压栈处理。如果我们进行以下调整：

调整子树的压栈顺序：访问根 - 遍历右子树 - 遍历左子树。（根 - 右 - 左）
把最终的结果逆序排列。（左 - 右 - 根）
最终得到的遍历结果，就是后序遍历的结果！我们将「根 - 左 - 右」变为了「左 - 右 - 根」。

我们尝试把上一小节提到的前序遍历的几种非递归方式，使用「翻转前序遍历结果」的方法，将前序遍历改造为「后序遍历」。

常规迭代方法的后续遍历「根右左逆序」版本：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode w = root;
        while(w!=null || stack.size()>0){
            while(w!=null){
                ans.add(w.val); 
                stack.push(w);
                w=w.right; // 变动点
            }
            w = stack.pop();
            w = w.left; // 变动点
        }
        Collections.reverse(ans); // 数组翻转
        return ans;
    }
}

模拟栈方法，后序遍历「根右左逆序」版本：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode w = root;
        if(w!=null)stack.push(w);
        while(stack.size()>0){
            w = stack.pop();
            ans.add(w.val);
            if(w.left!=null)stack.push(w.left); // 变动
            // ans.add(w.val); // 也可以写在这
            if(w.right!=null)stack.push(w.right); // 变动
            // ans.add(w.val); // 也可以写在这
        }
        Collections.reverse(ans); // 翻转数组
        return ans;
    }
}

线索二叉树——Morris 算法

本节介绍一种巧妙的方法可以在线性时间内，只占用常数空间来实现树的前、中、后序遍历。这种方法由 Joseph M. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。

Morris 遍历可以将非递归遍历中的空间复杂度降为 $O(1)$ 。从而实现时间复杂度为 $O(N)$ ，而空间复杂度为 $O(1)$ 的精妙算法。

实现原则

记作当前节点为 cur。

如果 cur 无左孩子，cur 向右移动（cur=cur.right）
如果 cur 有左孩子，找到 cur 左子树上最右的节点，记为 mostright
1. 如果 mostright 的 right 指针指向空，让其指向 cur，cur 向左移动（cur=cur.left）
2. 如果 mostright 的 right 指针指向 cur，让其指向空，cur 向右移动（cur=cur.right）

实现以上的原则，即实现了 Morris 遍历。

void Traversal(struct TreeNode* root, int* returnSize) {
    struct TreeNode *cur = root, *mostright = NULL;

    while (cur != NULL) {
        mostright = cur->left;
        if (mostright != NULL) {
            // 条件A、条件B都不满足 就一直找最右
            while (mostright->right != NULL && mostright->right != cur)
                mostright = mostright->right;
                
            // 只满足条件A
            if (mostright->right == NULL) {
                cur 前序遍历点位 1/2
                mostright->right = cur;
                cur = cur->left;
                continue;
            }
            // 只满足条件B 
            else {
                mostright->right = NULL;    
                cur 中序遍历点位 1/2
                // 预告：接下来将cur移动到右子树上
            }
        }
        // mostright == NULL 
        else {
            cur 前序遍历点位 2/2      
            cur 中序遍历点位 2/2
            // 预告：接下来将cur移动到右子树上
        }
        cur = cur->right;                // 将cur移动到右子树上
    } // end while
}