树是表达层级关系的通用结构：n 个节点恰好由 n-1 条边连接，任意两点间只有唯一路径，且不存在环。本文聚焦二叉树的性质、三种特殊形态的定义边界、四种遍历方式的统一框架，以及由遍历序列还原整棵树的充要条件。

它解决什么问题

数组和链表只能表达「一个挨一个」的线性关系，而现实中大量数据天然是层级的：文件系统的目录、HTML 的 DOM、编译器的语法树、索引中的键值分布。树用父子引用把这种一对多关系直接编码进结构里，让每个节点只需记住自己的后代。

在树家族中，二叉树是研究的起点：每个节点最多两个孩子，且左右位置不可颠倒。加上「左子树所有键小于根、右子树所有键大于根」这一约束，就得到二叉搜索树（BST），查找路径每次可以排除一半数据，平均复杂度 O(log n)。但 BST 的形状取决于插入顺序——按升序连续插入会退化成一条斜链，查找跌回 O(n)。这正是 AVL、红黑树等自平衡结构存在的理由，也是理解 B/B+ 树之前必须跨过的门槛。

核心原理

二叉树的三条数学性质

设根节点深度为 0、层数为 1：

  1. 第 i 层最多有 2^(i-1) 个节点，等比增长决定了「宽」；
  2. 深度为 k 的二叉树最多有 2^(k+1) - 1 个节点（满的情形），最少只有 k+1 个（退化成链的情形）——同样的节点数，形状可以让高度在 log n 与 n 之间摆动；
  3. 任意二叉树中，叶子节点数 n₀ 与度为 2 的节点数 n₂ 满足 n₀ = n₂ + 1。推导很短：总节点 n = n₀ + n₁ + n₂，总边数 n - 1 = n₁ + 2n₂，两式相减即得。

满、完全、平衡：三个容易混淆的定语

  • 满二叉树：每一层的节点数都达到该层上限，k 层共 2^k - 1 个节点。所有分支节点都有两个孩子，所有叶子同层。
  • 完全二叉树：除最后一层外全部填满，最后一层的节点从左向右连续排列。它不要求最底层填满，但要求「先左后右、不留空洞」。
  • 平衡二叉树（AVL）：约束的不是节点排布，而是每个节点左右子树的高度差不超过 1，且左右子树也递归满足。它建立在 BST 之上，是对「值有序 + 形状受控」的双重承诺。

三者关系必须掰清：满二叉树一定是完全二叉树，反之不然；完全二叉树是对结构的要求，与节点值无关，所以完全树未必是搜索树；平衡树是对搜索树形状的要求，与是否「完全」无关。完全二叉树最实用的副产品是父子下标的算术关系：根存下标 0 时，节点 i 的左孩子在 2i+1、右孩子在 2i+2，这让数组成为它的零浪费存储方案，堆正是靠这一点实现紧凑布局。

深入机制

递归遍历：一个模板的三个插入点

前序、中序、后序的差异只在于「访问当前节点」这行代码放在递归的哪个位置：

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置：根 -> 左 -> 右
    dfs(root.left);
    // 中序位置：左 -> 根 -> 右
    dfs(root.right);
    // 后序位置：左 -> 右 -> 根
}

位置不同，语义就不同：前序先见根，适合复制树和序列化；中序作用于 BST 时恰好输出升序序列；后序先拿到两棵子树的结果，天然适合求高度、释放节点和树形动态规划。三种遍历的时间都是 O(n)，递归栈额外空间 O(h)，h 为树高——平衡时 h ≈ log n，退化时 h = n。

迭代遍历：显式栈统一前中后序

递归的本质是系统栈，用手动栈可以写出结构完全同构的迭代版：

List<Integer> preorder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {          // 一路向左，沿途入栈
            ans.add(cur.val);          // 前序：首次经过即访问
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();             // 左子树穷尽，回退
        cur = cur.right;               // 转向右子树
    }
    return ans;
}

中序只需把 ans.add(cur.val) 从入栈处挪到出栈处——「入栈即访问」是前序，「出栈再访问」是中序，这一行之差就是两种遍历的全部区别。后序有个常用技巧：按「根 -> 右 -> 左」做前序变体，最后把结果逆序，即得「左 -> 右 -> 根」。

层序遍历：队列按深度逐层推进

深度优先用栈，广度优先用队列。要点是每轮循环先记录当前队列长度，把「这一层的节点」和「下一层的候选」切开：

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();       // 关键：锁定本层节点数
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        ans.add(level);
    }
    return ans;
}

「每层最值」「锯齿形遍历」「最小深度」等题目都只是这个骨架上改几行。

由遍历序列重建树的条件

结论先行：中序 + 前序或中序 + 后序可以唯一还原（无重复值时），前序 + 后序不能。原因在于中序提供了左右子树的分界线：前序首元素（或后序尾元素）是根，在中序里定位根，左侧即左子树、右侧即右子树，递归切分即可。而前序与后序都只能告诉你谁是根，当某节点只有一个孩子时，无法判断它是左孩子还是右孩子，存在歧义。

TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> pos = new HashMap<>();  // 中序值 -> 下标，避免重复查找
    for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
    return build(preorder, 0, preorder.length - 1, 0, pos);
}

TreeNode build(int[] pre, int pl, int pr, int il, Map<Integer, Integer> pos) {
    if (pl > pr) return null;
    TreeNode root = new TreeNode(pre[pl]);
    int mid = pos.get(pre[pl]);        // 根在中序中的位置
    int leftSize = mid - il;           // 左子树节点数
    root.left  = build(pre, pl + 1, pl + leftSize, il, pos);
    root.right = build(pre, pl + leftSize + 1, pr, mid + 1, pos);
    return root;
}

哈希表把每次定位根的 O(n) 降到 O(1)，整体复杂度 O(n)。

工程实践

  • 序列化选择前序：写入时附带空指针占位符，单靠前序即可无损还原，不必凑两种序列。LeetCode 的树序列化、RPC 传输树形结构都走这条路。
  • 警惕递归深度：JVM 默认栈深大约几千到一万帧，对可能退化成链的树（如有序数据建成的 BST）做递归遍历会 StackOverflowError。服务端代码处理不可信输入时，优先选迭代写法。
  • 验证 BST 不能只比父子：左孩子小于父、右孩子大于父只是必要条件。正确做法是递归时携带上下界，左子树上界收紧为当前值、右子树下界收紧为当前值，且边界用 long 防止 Integer.MIN_VALUE 数据溢出。

对比与权衡

结构 核心约束 查找复杂度 典型用途
普通二叉树 至多两个孩子 O(n) 表达式树、哈夫曼树
二叉搜索树 左小右大 平均 O(log n)，最坏 O(n) 有序数据的教学模型
AVL 树 高度差 ≤ 1 稳定 O(log n) 读多写少的内存索引
红黑树 颜色规则保黑高 稳定 O(log n) TreeMap、HashMap 树化
B/B+ 树 多路、矮胖 O(log n)，单次 I/O 读多键 数据库与文件系统索引

内存树在意指针跳转次数，外存树在意一次 I/O 能带回多少有效键，这是 B+ 树把节点做大、把数据压到叶子并用链表串起来的根本原因。

面试视角

为什么前序加后序无法唯一确定一棵树？ 两种序列都只能通过首尾识别根，给不出左右子树的分界。当某节点只有一个孩子时，左右位置不可判定，多棵不同的树会产出相同的两条序列，必须搭配中序才能消歧。

完全二叉树和满二叉树的区别是什么？堆为什么用前者？ 满二叉树要求每层填满，完全二叉树只要求最后一层从左连续。堆需要在数组里紧凑存放且支持尾部增删，完全二叉树的「无空洞」性质让下标换算 O(1)，满二叉树则无法容纳任意数量的节点。

递归遍历的空间复杂度是多少？ 由树高 h 决定，是 O(h) 而非 O(log n)。平衡树中 h ≈ log n，但输入有序时 BST 退化为链，h = n，此时递归栈可能溢出。

中序遍历 BST 得到什么？怎么用它找第 K 小？ 得到严格升序（无重复键时）序列。中序遍历时带一个计数器，第 K 次访问到的节点即答案，可提前剪枝返回，平均无需遍历全树。

小结

  • 二叉树的复杂度由形状决定：n 个节点的高度可以在 log n 到 n 之间，平衡结构的意义就是钉住下界。
  • 满、完全、平衡是三个维度的约束：满管「每层都满」，完全管「最后一层靠左连续」，平衡管「高度差受限」，互不蕴含。
  • 前中后序只是访问时机之差，递归与显式栈互为镜像；层序遍历的精髓是用队列长度锁定一层。
  • 重建树的关键是中序提供的左右分界，前序或后序负责给根，哈希表负责消掉重复定位的线性开销。