算法刷题系列（二十八）：树的搜索——前序、中序、后序与层序

算法刷题系列（二十八）：树的搜索——前序、中序、后序与层序

树的遍历都访问节点，但访问时机不同。深度优先的前序、中序、后序共享同一递归骨架，只改变“处理当前节点”相对于左右子树的位置；层序遍历则使用队列按距离根节点的层次扩展。

一、三种深度优先顺序

对根为 A、左孩子 B、右孩子 C 的简单树：

• 前序：根、左、右，结果 A B C；
• 中序：左、根、右，结果 B A C；
• 后序：左、右、根，结果 B C A。

中序遍历只有在二叉搜索树且键按规则组织时才会得到有序序列；一般二叉树的中序结果并不自动排序。后序适合先获得孩子结果再处理父节点，例如释放树、计算汇总信息；前序适合复制或序列化时先记录根。

二、层序遍历

队列先放根，取出一个节点后按左、右顺序放入孩子。队列保证先发现的较浅节点先处理，因此结果按层输出。要分组记录每层，可在每轮开始时保存当前队列长度，恰好处理这批节点。

三、Java 实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    static final class Node {
        final int value;
        Node left;
        Node right;
        Node(int value) { this.value = value; }
    }

    static List<Integer> preorder(Node node) {
        List<Integer> result = new ArrayList<>();
        preorder(node, result);
        return result;
    }

    private static void preorder(Node node, List<Integer> result) {
        if (node == null) return;
        result.add(node.value);
        preorder(node.left, result);
        preorder(node.right, result);
    }

    static List<Integer> inorder(Node node) {
        List<Integer> result = new ArrayList<>();
        inorder(node, result);
        return result;
    }

    private static void inorder(Node node, List<Integer> result) {
        if (node == null) return;
        inorder(node.left, result);
        result.add(node.value);
        inorder(node.right, result);
    }

    static List<Integer> postorder(Node node) {
        List<Integer> result = new ArrayList<>();
        postorder(node, result);
        return result;
    }

    private static void postorder(Node node, List<Integer> result) {
        if (node == null) return;
        postorder(node.left, result);
        postorder(node.right, result);
        result.add(node.value);
    }

    static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                Node node = queue.poll();
                level.add(node.value);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            levels.add(level);
        }
        return levels;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        assert preorder(root).equals(List.of(1, 2, 4, 5, 3));
        assert inorder(root).equals(List.of(4, 2, 5, 1, 3));
        assert postorder(root).equals(List.of(4, 5, 2, 3, 1));
        assert levelOrder(root).equals(List.of(
                List.of(1), List.of(2, 3), List.of(4, 5)));
        assert levelOrder(null).isEmpty();
    }
}

四、Python 实现

from collections import deque
from typing import Optional

class Node:
    def __init__(
        self, value: int, left: "Node | None" = None, right: "Node | None" = None
    ) -> None:
        self.value = value
        self.left = left
        self.right = right

def preorder(node: Optional[Node]) -> list[int]:
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

def inorder(node: Optional[Node]) -> list[int]:
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def postorder(node: Optional[Node]) -> list[int]:
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]

def level_order(root: Optional[Node]) -> list[list[int]]:
    if root is None:
        return []
    levels: list[list[int]] = []
    queue = deque([root])
    while queue:
        level: list[int] = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        levels.append(level)
    return levels

root = Node(1, Node(2, Node(4), Node(5)), Node(3))
assert preorder(root) == [1, 2, 4, 5, 3]
assert inorder(root) == [4, 2, 5, 1, 3]
assert postorder(root) == [4, 5, 2, 3, 1]
assert level_order(root) == [[1], [2, 3], [4, 5]]
assert level_order(None) == []

五、复杂度与实现提醒

四种遍历都访问每个节点一次，时间复杂度 O(n)。深度优先递归的额外栈空间是 O(h)；层序队列最多存放某一层的节点，最坏为 O(n)。输出序列本身占 O(n)，不计入辅助空间时应单独说明。

Java 的 ArrayDeque 不允许放入 null，所以只把非空孩子入队；空根提前返回。层序代码若在循环体里用不断变化的 queue.size() 控制整层，会把后续层新入队的节点也处理掉；应先固定 levelSize。对极深的树，递归遍历可能栈溢出，可改用显式栈。

小结与衔接

树遍历的变化点是访问节点的时机：根在前、中、后，或使用队列按层处理。下一篇将从树扩展到一般图，重点区分树中天然无环的递归与图中必须显式维护的访问状态。