二叉树--纲领篇

在本文的最开始，首先介绍一下二叉树的解题思路。所有的二叉树解题思路，仅分为两种：

遍历法：根据不同遍历的顺序 (先序，中序，后序) 时机，利用全局变量来解决当前问题
分解子问题：把一个问题分解为「当前节点」「左子树」「右子树」需要处理的工作

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

深入理解前中后序

我们可能存在一种固有思维，把「前中后」三种遍历理解为三种不同的顺序。其实这种理解仅仅是在第一层而已

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

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

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

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

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

小小实战

先来一个最最最简单的题目，前序遍历。详情可见题目二叉树的前序遍历

首先我们用最常见的「遍历法」

注：遍历法一般都是通过全局变量来记录结果


// 定义全局变量，存储结果
public List<Integer> res = new ArrayList<>();
public void traversal(TreeNode root) {
    if (root == null) return ;
    // 前序：刚刚进入当前节点
    res.add(root.val);
    traversal(root.left);
    traversal(root.right);
}

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


xxxxxxxxxx
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 的中序遍历认为是遍历有序数组
前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了

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

但这里面大有玄妙，意味着前序位置的代码只能从函数参数中获取父节点传递来的数据；而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据

例：现在有一棵二叉树，有两个简单的问题：

如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？
如何打印出每个节点的左右子树各有多少节点？

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


xxxxxxxxxx
public void traversal(TreeNode root, int level) {
    if (root == null) return ;
    System.out.println("节点 " + root.val + " 在第 " + lever + " 层");
    traversal(root.left, level + 1);
    traversal(root.right, level + 1);
}

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


xxxxxxxxxx
public int traversal(TreeNode root) {
    if (root == null) return ;
    int leftCount = traversal(root.left);
    int rightCount = traversal(root.right);
    System.out.println("节点 " + root.val + " 的左子树有 " + leftCount + " 个节点，右子树有 " + rightCount + " 个节点");
    return leftCount + rightCount + 1;
}

这两个问题的根本区别在于：一个节点在第几层，从根节点遍历过来的过程就能顺带记录；而以一个节点为根的整棵子树有多少个节点，需要遍历完子树之后才能数清楚

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

层序遍历

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


xxxxxxxxxx
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;
}

关于更多层序遍历的应用，可见二叉树关于行的相关操作技巧