数据结构与算法 / 系统课时

用前中后序选择树的计算时机

用前中后序选择树的计算时机

二叉树题真正难的往往不是“会不会递归”,而是把计算放在递归的哪个位置。前序、中序、后序本质上对应三种计算时机:进入节点就处理、左右子树之间处理、拿到子树结果后再处理。

学习目标

  • 根据答案对父节点或子节点结果的依赖选择遍历顺序
  • 理解前序、中序、后序只是同一递归骨架中的不同计算位置
  • 用可运行示例验证三种顺序产生的访问序列

先看依赖关系再选顺序

选择遍历方式时,不要先背“根左右、左根右、左右根”,而要先问:当前节点的答案依赖什么信息?

如果处理孩子之前就已经拥有所需信息,适合前序。例如路径题常把父节点累计值传给孩子,进入当前节点时就能更新路径状态。

如果问题依赖二叉搜索树的有序性质,常用中序。对于 BST,中序访问会按键值从小到大得到节点,适合第 K 小元素、验证有序性等题。

如果当前节点必须等左右子树都计算完成后才能得出答案,适合后序。树高、平衡判断、子树节点数、直径等自底向上问题都属于这一类。

同一棵树中前序中序后序的计算时机

同一递归骨架中的三个位置

下面的完整程序使用同一棵树分别执行三种遍历。注意三个方法结构几乎相同,区别只有 result.add(node.val) 放在递归调用之前、之间还是之后。

java
import java.util.ArrayList;
import java.util.List;

public class TraversalTimingDemo {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static void preorder(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }

        result.add(node.val); // 进入节点时计算
        preorder(node.left, result);
        preorder(node.right, result);
    }

    static void inorder(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }

        inorder(node.left, result);
        result.add(node.val); // 左子树完成、右子树开始前计算
        inorder(node.right, result);
    }

    static void postorder(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }

        postorder(node.left, result);
        postorder(node.right, result);
        result.add(node.val); // 两棵子树都完成后计算
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        List<Integer> pre = new ArrayList<>();
        List<Integer> in = new ArrayList<>();
        List<Integer> post = new ArrayList<>();

        preorder(root, pre);
        inorder(root, in);
        postorder(root, post);

        System.out.println("pre=" + pre);
        System.out.println("in=" + in);
        System.out.println("post=" + post);
    }
}

预期输出:

text
pre=[1, 2, 4, 5, 3]
in=[4, 2, 5, 1, 3]
post=[4, 5, 2, 3, 1]

输出顺序不是为了记忆,而是在验证“计算发生点”。把 result.add 换成真正的业务计算,三种遍历就分别变成自顶向下、中间访问和自底向上的通用模板。

用返回值判断是否该后序

当递归函数需要从左右子树“收集答案”时,通常已经在暗示后序。以树高为例,当前节点高度必须先拿到左子树高度和右子树高度,才能计算 1 + max(left, right)。

这类题常见的函数形态是“递归调用返回子树信息,当前节点合并两个结果,再把新结果返回父节点”。如果你发现自己在访问父节点时还不知道答案,说明计算位置放早了,应把逻辑移动到两个递归调用之后。

反过来,如果函数参数携带的是“从父节点传下来的状态”,例如当前路径和、当前深度、已经选择的节点,那么往往应在递归进入节点时先更新状态,再把新状态传给孩子,这更接近前序。

中序不是通用的中间态

中序在普通二叉树上只是固定的访问顺序,并不会天然产生特殊性质。它真正高频的场景是二叉搜索树,因为 BST 满足左子树键值小于当前节点、右子树键值大于当前节点,所以中序结果具有有序性。

因此看到普通树的最大深度、直径、最近公共祖先等题时,不要因为“中序位于左右递归之间”就机械套用。先判断依赖方向,再决定计算时机,比背遍历名称更可靠。

把题目翻译成依赖关系后,选择会很直接:父状态向下传播用前序,BST 借助有序性常用中序,子树结果向上汇总用后序。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用前中后序选择树的计算时机

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通