前言

看完希望你对二叉树的遍历有更深入的理解

首先介绍一下二叉树的解题思路。所有的二叉树解题思路，大致可以分为两种：

• 遍历法（递归遍历、迭代遍历）：根据不同遍历的顺序 (先序or前序，中序，后序) 时机，利用全局变量来解决当前问题

• 分解法（分解子问题）：把一个问题分解为「当前节点」「左子树」「右子树」需要处理的工作

但无论使用哪种思路，都需要明确对于当前正在处理的二叉树节点，它需要「做什么」「什么时候做」。至于其他的节点，都可以通过「递归」的方法执行相同的操作

前中后序的理解

我们可能存在一种固有思维，把「前中后」三种遍历理解为三种不同的顺序。其实这种理解仅仅停留在表象，本质上可以说它就是一种遍历，只是处理的时间点不同，比如：

• 前序遍历：刚刚进入一个节点的时候执行

• 中序遍历：当一个节点的左子树处理完，即将要处理右子树之前执行

• 后序遍历：即将离开一个节点的时候执行

说了这么多，就是要帮你建立对二叉树正确的认识，然后你会发现：

二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用管，交给二叉树遍历框架，递归会在所有节点上做相同的操作

实践检验真理

我们先看一个最基础的题目，前序遍历。

首先我们用最常见的「遍历法」，注：遍历法一般都是通过全局变量来记录结果

// 定义全局变量，存储结果
List<Integer> res = new ArrayList<>();

public void traversal(TreeNode root) {
    
    if (root == null) return ;
    // 前序：刚刚进入当前节点
    res.add(root.val);
    
    traversal(root.left);
    traversal(root.right);
}

然后我们使用「分解子问题」的方法来解决一下这个问题

public List<Integer> traversal(TreeNode root) {
    
    List<Integer> res = new ArrayList<>();
    
    if (root == null) return res;
    // 前序：刚刚进入当前节点
    res.add(root.val);
    
    res.addAll(traversal(root.left)); // 加入左子树处理完的结果
    res.addAll(traversal(root.right)); // 加入右子树处理完的结果
    // 返回
    return res;
}

现在理解了两种不同思路，当我们在遇到题目的时候，思考：是否可以通过遍历一遍二叉树得到答案？

如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要设计到子树信息, 建议使用后续遍历

后序位置的特殊之处

说后序位置之前，先简单说下中序和前序

• 中序位置主要用在 BST 场景中，根据BST的特性，可以把 BST 的中序遍历认为是升序排序

• 前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了

可以发现，前序位置的代码执行是「自顶向下」的，而后序位置的代码执行是「自底向上」的。这不奇怪，因为本文开头就说了前序位置是刚刚进入节点的时刻，后序位置是即将离开节点的时刻

但这里面大有玄妙：

• 意味着前序位置的代码只能从函数参数中获取父节点传递来的数据；

• 而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据

例如：现在有一棵二叉树，你先思考两个问题？

如果把根节点看做第 1 层，

1. 如何打印出每一个节点所在的层数？

2. 如何打印出每个节点的左右子树各有多少节点？

第一个问题可以这样写代码：

void traversal(TreeNode root, int level) {
    
    if (root == null) return ;
    
    printf("节点 %s 在第 %d 层", root, level);
    traversal(root.left, level + 1);
    traversal(root.right, level + 1);
}

第二个问题可以这样写代码：

int traversal(TreeNode root) {
    
    if (root == null) return ;
    
    int leftCount = traversal(root.left);
    int rightCount = traversal(root.right);
    printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点", root, leftCount, rightCount);
    return leftCount + rightCount + 1;
}

这两个问题的根本区别在于：

• 一个节点在第几层，从根节点遍历过来的过程就能顺带记录；

• 而以一个节点为根的整棵子树有多少个节点，需要遍历完子树之后才能数清楚

结合这两个基础的问题，可以细品一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息

那么换句话说，一旦发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，然后在后序位置写代码了，可以看下这几道题104二叉树的最大深度，543二叉树的直径，124二叉树的最大路径和。

层序遍历

二叉树题型主要是用来培养递归思维的，而层序遍历属于迭代遍历，这里就过一下代码框架吧：

public List<Integer> levelTraverse(TreeNode root) {
    
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
	
	// 从上到下遍历二叉树的每一层
    while (!q.isEmpty()) {
    
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
    
            TreeNode cur = q.poll();
            res.add(cur.val);
            // 将下一层放入队列
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
    }
    return res;
}

当然这个框架还可以灵活修改，题目不需要记录层数（步数）时可以去掉上述框架中的 for 循环。