算法模板 - 二叉树遍历

本篇将先介绍前后中序的递归写法，一些同学可能会感觉很简单，其实不然，我们要通过简单题目把方法论确定下来，有了方法论，后面才能应付复杂的递归。

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

好了，我们确认了递归的三要素，接下来就来练练手：

• 144.二叉树的前序遍历 (opens new window)
• 145.二叉树的后序遍历 (opens new window)
• 94.二叉树的中序遍历 (opens new window)

1. 二叉树的递归遍历

1.1 前序遍历

前序遍历（根节点 - 左子树 - 右子树）。在递归调用时，往往是先处理当前节点，再分别递归到左子树和右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    /**
     * 前序遍历 - 递归实现
     * @param root 二叉树根节点
     * @return 前序遍历结果（节点值的列表）
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }

    /**
     * 递归函数，使用前序遍历的方式访问二叉树
     * @param root 当前子树的根节点
     * @param result 记录节点访问顺序的列表
     */
    private void preorder(TreeNode root, List<Integer> result) {
        // 1. 终止条件：当前节点为 null
        if (root == null) {
            return;
        }

        // 2. 单层递归逻辑
        // （1）处理当前节点
        result.add(root.val);

        // （2）递归遍历左子树
        preorder(root.left, result);

        // （3）递归遍历右子树
        preorder(root.right, result);
    }
}

解析：

1. 参数与返回值
   • 参数：TreeNode root（当前子树的根节点）、List<Integer> result（保存遍历结果）。
   • 返回值：通过对 result 的更新来间接实现，不需要函数本身直接返回值。
2. 终止条件
   • 当 root == null 时，递归到叶子或空节点，停止处理。
3. 单层递归逻辑
   • 前序：先访问当前节点（result.add(root.val)），然后递归进入左子树，再递归进入右子树。

前序遍历的访问顺序：根 → 左 → 右。

1.2 中序遍历

中序遍历（左子树 - 根节点 - 右子树）。在递归中通常是先处理左子树，再处理当前节点，最后处理右子树。

class Solution {
    /**
     * 中序遍历 - 递归实现
     * @param root 二叉树根节点
     * @return 中序遍历结果（节点值的列表）
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    /**
     * 递归函数，中序遍历
     * @param root 当前子树根节点
     * @param list 保存遍历顺序的列表
     */
    private void inorder(TreeNode root, List<Integer> list) {
        // 1. 终止条件
        if (root == null) {
            return;
        }

        // 2. 递归遍历左子树
        inorder(root.left, list);

        // 3. 处理当前节点
        list.add(root.val);

        // 4. 递归遍历右子树
        inorder(root.right, list);
    }
}

解析：

1. 参数与返回值
   • 同样通过 root 和 List<Integer> 这两个参数实现，不需要函数直接返回中序结果。
2. 终止条件
   • root == null 时返回。
3. 单层递归逻辑
   • 中序：先左后根再右。即先递归遍历左子树、访问当前节点、最后递归遍历右子树。

中序遍历的访问顺序：左 → 根 → 右。

1.3 后序遍历

后序遍历（左子树 - 右子树 - 根节点）。递归时一般是先处理左子树，再处理右子树，最后处理当前节点。

class Solution {
    /**
     * 后序遍历 - 递归实现
     * @param root 二叉树根节点
     * @return 后序遍历结果（节点值的列表）
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    /**
     * 递归函数，后序遍历
     * @param root 当前子树根节点
     * @param list 保存遍历顺序的列表
     */
    private void postorder(TreeNode root, List<Integer> list) {
        // 1. 终止条件
        if (root == null) {
            return;
        }

        // 2. 递归遍历左子树
        postorder(root.left, list);

        // 3. 递归遍历右子树
        postorder(root.right, list);

        // 4. 处理当前节点
        list.add(root.val);
    }
}

解析：

1. 参数与返回值
   • 同前序/中序类似，使用 root 和结果列表 res 的方式。
2. 终止条件
   • root == null。
3. 单层递归逻辑
   • 后序：先左子树、再右子树，最后当前节点。

后序遍历的访问顺序：左 → 右 → 根。

1.4 递归三要素总结

1. 参数与返回类型：
   • 对于树的递归遍历，不需要返回值给上层递归，而是采用「全局或外部列表」来存放遍历结果。
   • 如果需要额外信息（如深度、路径等），可以在函数参数中添加或封装为一个辅助类。
2. 终止条件：
   • 最普遍的是 if (root == null) return;，表示遇到空节点就停止处理。
3. 单层递归逻辑：
   • 前序：（根 → 左 → 右）
   • 中序：（左 → 根 → 右）
   • 后序：（左 → 右 → 根）

写每个递归函数时，都想想：

1. 参数和返回类型：是否需要返回值或额外信息给上层？
2. 终止条件：当前节点为空等。
3. 一层递归内的操作顺序：先访问谁，再递归处理左右子树。

2. 二叉树的迭代遍历

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？

我们之前有提到过，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了

2.1 前序遍历（迭代法）

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    /**
     * 使用栈实现二叉树的前序遍历。
     * @param root 二叉树的根节点。
     * @return 返回前序遍历的结果列表。
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        // 创建一个列表来存储遍历的结果
        List<Integer> result = new ArrayList<>();

        // 如果根节点为空，则直接返回空列表
        if (root == null) {
            return result;
        }

        // 创建一个栈来辅助前序遍历
        Stack<TreeNode> stack = new Stack<>();
        // 首先将根节点压入栈
        stack.push(root);

        // 遍历栈，直到栈为空
        while (!stack.isEmpty()) {
            // 弹出栈顶元素
            TreeNode node = stack.pop();
            // 将栈顶元素（当前节点）的值加入结果列表
            result.add(node.val);

            // 如果右孩子不为空，则将右孩子压入栈
            if (node.right != null) {
                stack.push(node.right);
            }

            // 如果左孩子不为空，则将左孩子压入栈
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        // 返回遍历结果
        return result;
    }
}

2.2 中序遍历（迭代法）

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

1. 处理：将元素放进result数组中
2. 访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，可以用栈来模拟递归的调用过程，递归的调用过程是不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。

动画如下：

class Solution {
    /**
     * 使用栈实现二叉树的中序遍历。
     * @param root 二叉树的根节点。
     * @return 返回中序遍历的结果列表。
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        // 创建一个列表来存储遍历的结果
        List<Integer> res = new ArrayList<Integer>();
        // 创建一个栈来辅助中序遍历
        Stack<TreeNode> stack = new Stack<TreeNode>();

        // 当根节点不为空或者栈不为空时，循环继续
        while (root != null || !stack.isEmpty()) {
            // 不断向左子树深入，并将经过的节点保存到栈中
            if (root != null) {
                stack.add(root);
                root = root.left;
            } else {
                // 当前节点为空，说明左边走到头了
                // 弹出栈顶元素并访问（处理）
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                // 转向处理右子节点
                root = tmp.right;
            }
        }
        return res;
    }
}

2.3 后序遍历（迭代法）

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    /**
     * 使用栈实现二叉树的后序遍历。
     * @param root 二叉树的根节点。
     * @return 返回后序遍历的结果列表。
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        // 创建一个列表来存储遍历的结果
        List<Integer> result = new ArrayList<>();

        // 如果根节点为空，则直接返回空列表
        if (root == null) {
            return result;
        }

        // 创建一个栈来辅助后序遍历
        Stack<TreeNode> stack = new Stack<>();
        // 首先将根节点压入栈
        stack.push(root);

        // 遍历栈，直到栈为空
        while (!stack.isEmpty()) {
            // 弹出栈顶元素
            TreeNode node = stack.pop();
            // 将栈顶元素（当前节点）的值加入结果列表的头部
            result.add(node.val);

            // 如果左孩子不为空，则将左孩子压入栈
            if (node.left != null) {
                stack.push(node.left);
            }
            // 如果右孩子不为空，则将右孩子压入栈
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        // 最后将结果列表反转，得到后序遍历的顺序
        Collections.reverse(result);
        return result;
    }
}