树、DFS 与 BFS

介绍

树是算法面试中最重要的非线性数据结构。理解树的遍历（DFS、BFS）是解决树类问题的前提。

核心心态

树 = 递归结构。每个子树本身又是一棵树。这是最重要的心理模型 — 遇到树题，先想递归：对当前节点做点什么，然后对左右子树递归调用。大多数树题的解法只需要 3-5 行递归代码。

---

二叉树定义

术语	定义
Binary Tree 二叉树	每个节点最多两个子节点
Binary Search Tree (BST) 二叉搜索树	左子树全部小于根，右子树全部大于根（有序）
Balanced Tree 平衡树	任意节点左右子树深度差不超过 1
Full Binary Tree 完全二叉树	每个非叶子节点都有两个子节点
Perfect Binary Tree 完美二叉树	所有叶子在同一层，每个父节点都有两个子节点

---

Depth-First Search (DFS)

深度优先遍历沿着一条路径走到头再回溯。三种遍历顺序（记根节点的位置）：

• 前序 (pre-order)：根 → 左 → 右
• 中序 (in-order)：左 → 根 → 右
• 后序 (post-order)：左 → 右 → 根

三种顺序各自用在什么场景？

顺序	特性	适用场景
前序	先访问父，再访问子	复制树（先建父节点）、序列化
中序	BST 的中序遍历 = 升序输出	BST 相关问题（验证 BST、找第 k 小元素）
后序	先处理子，再处理父	删除树（先删子再删父）、计算子树属性（自底向上）

最重要的 BST 洞察：二叉搜索树的中序遍历天然得到有序序列。很多 BST 题（验证 BST、两数之和 IV、最小绝对差）的核心解法就是中序遍历 + 处理有序序列。

递归实现

递归写法最直观，三种顺序只是访问根节点的位置不同：

// pre-order: root → left → right
public void preOrder(TreeNode root) {
    if (root == null) return;
    visit(root);
    preOrder(root.left);
    preOrder(root.right);
}

// in-order: left → root → right
public void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    visit(root);
    inOrder(root.right);
}

// post-order: left → right → root
public void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    visit(root);
}

迭代实现（使用栈）

非递归写法用栈模拟递归。关键：前序先压右再压左（保证左先出栈）。

// pre-order — iterative
public void preOrderIter(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        visit(cur);
        // push right first so left is processed first
        if (cur.right != null) stack.push(cur.right);
        if (cur.left != null) stack.push(cur.left);
    }
}

// in-order — iterative
public void inOrderIter(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;

    while (!stack.isEmpty() || node != null) {
        if (node != null) {
            stack.push(node);
            node = node.left;        // go left as far as possible
        } else {
            node = stack.pop();      // backtrack
            visit(node);
            node = node.right;       // go right
        }
    }
}

// post-order — iterative
public void postOrderIter(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    TreeNode lastVisited = null;

    while (!stack.isEmpty() || node != null) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            TreeNode peek = stack.peek();
            // if right child exists and hasn't been visited, go right
            if (peek.right != null && lastVisited != peek.right) {
                node = peek.right;
            } else {
                visit(peek);
                lastVisited = stack.pop();
            }
        }
    }
}

模式识别

• “按层处理” → BFS（层序遍历、最短路径、右视图）
• “自顶向下传值” → 前序（路径和最大深度）
• “自底向上聚合” → 后序（子树和、平衡判断）
• “BST + 有序” → 中序（验证 BST、第 k 小元素）
• 树天然适合递归 — 先确定对当前节点做什么，再递归左右子树

---

Breadth-First Search (BFS)

广度优先一层一层遍历，用队列实现。

public void bfs(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        visit(node);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

分层遍历（LeetCode 常见要求 — 按层输出结果）：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; 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);
        }
        result.add(level);
    }
    return result;
}

---

Heap

堆是一种特殊的完全二叉树，满足堆属性：父节点总大于（或小于）子节点。

• Min-Heap 最小堆：根节点 ≤ 所有子节点
• Max-Heap 最大堆：根节点 ≥ 所有子节点

构造和维护靠”冒泡”式交换：

Max Heap Insertion:
  Step 1 — 在堆末尾创建新节点
  Step 2 — 赋新值给该节点
  Step 3 — 与父节点比较
  Step 4 — 如果父节点更小，交换它们
  Step 5 — 重复 3-4 直到堆属性满足

Max Heap Deletion (删除根):
  Step 1 — 移除根节点
  Step 2 — 将最后一层的最后一个元素移至根
  Step 3 — 与子节点比较
  Step 4 — 如果父节点更小，与较大的子节点交换
  Step 5 — 重复 3-4 直到堆属性满足

Java 中 PriorityQueue 默认是最小堆。

---

关键技巧

• DFS 用栈（递归或显式栈），BFS 用队列 — 这是两种遍历的本质区别
• 三种 DFS 的顺序记根的位置：pre（根→左→右）、in（左→根→右）、post（左→右→根）
• 递归直观，迭代省栈空间 — 面试时两种都该会写
• BFS 分层遍历：在每层开始时记录 levelSize = queue.size()，只处理那么多节点
• 堆 = 完全二叉树 + 冒泡维护，PriorityQueue 是最常用的堆实现

参考资料

• Heap Data Structure — TutorialsPoint
• LeetCode — Binary Tree Level Order Traversal