跳至主要內容

高频算法题型：二叉树遍历与重构

郑天祺2026/6/27大约 9 分钟刷题算法二叉树遍历重构LeetCode

高频算法题型：二叉树遍历与重构

高频算法题型：二叉树遍历与重构是计算机科学的核心，它为问题解决提供了高效的计算方法。
本文介绍了高频算法题型：二叉树遍历与重构的设计思路和实现方式，帮助你提升编程能力。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

1.2 遍历方式分类

遍历方式顺序特点
前序遍历根→左→右先访问根节点
中序遍历左→根→右BST 中序是有序的
后序遍历左→右→根先处理子树再处理根
层序遍历逐层从左到右BFS

二、四种遍历实现

2.1 递归实现（最简洁）

// 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorder(root, result);
    return result;
}

private void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);        // 根
    preorder(node.left, result);  // 左
    preorder(node.right, result); // 右
}

// 中序遍历
private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);   // 左
    result.add(node.val);         // 根
    inorder(node.right, result);  // 右
}

// 后序遍历
private void postorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorder(node.left, result);   // 左
    postorder(node.right, result);  // 右
    result.add(node.val);           // 根
}

2.2 迭代实现（面试常考）

前序遍历（栈）：

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    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;
}

中序遍历（栈）：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
        // 一路向左压栈
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        // 弹出访问
        curr = stack.pop();
        result.add(curr.val);
        // 转向右子树
        curr = curr.right;
    }
    return result;
}

后序遍历（栈，技巧法）：

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val);  // 逆序添加（头插法）
        // 顺序与前序相反：先左后右
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return result;
}

技巧： 后序遍历（左→右→根）的逆序 = 修改后的前序遍历（根→右→左）的逆序。所以用 addFirst 就能巧妙实现后序遍历。

2.3 层序遍历（BFS）

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;
}

三、10 道经典题详解

第 1 题：二叉树的最大深度（LeetCode 104）

// 递归
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// BFS 层序
public int maxDepthBFS(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        depth++;
    }
    return depth;
}

第 2 题：对称二叉树（LeetCode 101）

题目： 判断二叉树是否是镜像对称的。

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    return left.val == right.val 
        && isMirror(left.left, right.right)   // 左的左 vs 右的右
        && isMirror(left.right, right.left);  // 左的右 vs 右的左
}

第 3 题：翻转二叉树（LeetCode 226）

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    // 交换左右子树
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    // 递归翻转
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

第 4 题：二叉树的最近公共祖先（LeetCode 236）

题目： 找到两个节点的最近公共祖先。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case
    if (root == null || root == p || root == q) {
        return root;
    }
    
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    if (left != null && right != null) {
        // p 和 q 分别在左右子树，当前节点就是 LCA
        return root;
    }
    if (left != null) return left;
    if (right != null) return right;
    return null;
}

理解关键： 递归的本质是"在当前子树中找 p 和 q 的 LCA"。如果 p 和 q 分别在左右子树，当前节点就是 LCA；如果都在同一侧，LCA 在那一侧。

第 5 题：验证二叉搜索树（LeetCode 98）

public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) 
        && validate(node.right, node.val, max);
}

避坑： 不能只比较节点和左右子节点！必须维护一个合法范围 (min, max)。

第 6 题：二叉树展开为链表（LeetCode 114）

题目： 按前序遍历顺序将二叉树展开为右链表。

public void flatten(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left != null) {
            // 找到左子树的最右节点
            TreeNode prev = curr.left;
            while (prev.right != null) {
                prev = prev.right;
            }
            // 将右子树接到左子树的最右节点
            prev.right = curr.right;
            // 左子树变右子树
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
}

第 7 题：从前序与中序遍历序列构造二叉树（LeetCode 105）

题目： 给定前序和中序遍历结果，重构二叉树。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1, inorderMap);
}

private TreeNode build(int[] preorder, int preStart, int preEnd,
                       int[] inorder, int inStart, int inEnd,
                       Map<Integer, Integer> inorderMap) {
    if (preStart > preEnd) return null;
    
    // 前序第一个就是根节点
    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);
    
    // 在中序中找到根的位置
    int rootIdx = inorderMap.get(rootVal);
    int leftSize = rootIdx - inStart;
    
    // 递归构建左右子树
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, rootIdx - 1, inorderMap);
    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, rootIdx + 1, inEnd, inorderMap);
    
    return root;
}

核心思路：

  1. 前序第一个是根
  2. 在中序中定位根，左边是左子树，右边是右子树
  3. 递归构建

第 8 题：从中序与后序遍历序列构造二叉树（LeetCode 106）

public TreeNode buildTree(int[] inorder, int[] postorder) {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return build(inorder, 0, inorder.length - 1,
                 postorder, 0, postorder.length - 1, inorderMap);
}

private TreeNode build(int[] inorder, int inStart, int inEnd,
                       int[] postorder, int postStart, int postEnd,
                       Map<Integer, Integer> inorderMap) {
    if (postStart > postEnd) return null;
    
    // 后序最后一个是根
    int rootVal = postorder[postEnd];
    TreeNode root = new TreeNode(rootVal);
    
    int rootIdx = inorderMap.get(rootVal);
    int leftSize = rootIdx - inStart;
    
    root.left = build(inorder, inStart, rootIdx - 1,
                      postorder, postStart, postStart + leftSize - 1, inorderMap);
    root.right = build(inorder, rootIdx + 1, inEnd,
                       postorder, postStart + leftSize, postEnd - 1, inorderMap);
    
    return root;
}

第 9 题：二叉树的直径（LeetCode 543）

题目： 二叉树中任意两节点间的最长路径长度。

private int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return maxDiameter;
}

private int maxDepth(TreeNode node) {
    if (node == null) return 0;
    int leftDepth = maxDepth(node.left);
    int rightDepth = maxDepth(node.right);
    // 直径 = 左深度 + 右深度
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
    return 1 + Math.max(leftDepth, rightDepth);
}

关键： 最长路径不一定经过根节点！所以需要在每个节点处都更新最大直径。

第 10 题：路径总和 III（LeetCode 437）

题目： 找出二叉树中节点值之和等于 targetSum 的路径数量。

public int pathSum(TreeNode root, int targetSum) {
    // 前缀和 + DFS
    Map<Long, Integer> prefixSumCount = new HashMap<>();
    prefixSumCount.put(0L, 1); // 前缀和为 0 出现 1 次
    return dfs(root, 0L, targetSum, prefixSumCount);
}

private int dfs(TreeNode node, long currSum, int targetSum, 
                Map<Long, Integer> prefixSumCount) {
    if (node == null) return 0;
    
    currSum += node.val;
    // 看看之前有几个前缀和等于 currSum - targetSum
    int count = prefixSumCount.getOrDefault(currSum - targetSum, 0);
    
    // 更新前缀和
    prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1);
    
    count += dfs(node.left, currSum, targetSum, prefixSumCount);
    count += dfs(node.right, currSum, targetSum, prefixSumCount);
    
    // 回溯：撤销当前节点的前缀和
    prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1);
    
    return count;
}

核心思想： 前缀和优化。从根到当前节点的和为 currSum，如果 currSum - targetSum 在之前出现过，说明中间那段路径的和正好是 targetSum。

四、二叉树题型分类与解题策略

4.1 题型分类

二叉树题目
├── 遍历类（前中后序、层序）→ 掌握递归和迭代两种写法
├── 深度/高度类 → 递归 return 1 + max(left, right)
├── 路径类 → DFS + 前缀和/回溯
├── 构造类 → 递归分治（找根 → 分左右）
├── 修改类 → 递归修改子树指针
└── BST 专项 → 利用有序性

4.2 解题思维框架

遇到二叉树题目的思考顺序：

  1. 能用递归吗？ → 大部分二叉树题都能用递归
  2. 递归函数返回什么？ → 深度？节点？布尔值？
  3. base case 是什么？ → 通常是 null
  4. 当前节点做什么？ → 访问值？交换子树？更新全局变量？

4.3 两种递归范式

范式一：返回值型（自底向上）

// 子树的结果汇总到当前节点
int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = dfs(node.left);
    int right = dfs(node.right);
    return 1 + Math.max(left, right); // 汇总
}

范式二：全局变量型（自顶向下）

int result = 0;
void dfs(TreeNode node, int depth) {
    if (node == null) return;
    result = Math.max(result, depth); // 更新全局结果
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
}

五、面试要点与总结

高频面试题

Q1：前序+中序为什么能唯一确定二叉树？

答：前序第一个元素是根，在中序中定位根的位置，左边是左子树的中序，右边是右子树的中序。根据左子树大小可以分割前序序列。递归处理即可。注意：前序+后序不能唯一确定二叉树（当一个节点只有一个子节点时，无法区分是左子还是右子）。

Q2：递归和迭代遍历怎么选？

答：面试中两者都可能考。递归简洁但可能栈溢出（树很深时）；迭代用显式栈更安全。通常先用递归写出正确解法，再被要求优化为迭代。

Q3：最近公共祖先的时间复杂度？

答：O(n)，每个节点最多访问一次。空间复杂度 O(h)，h 为树高，最坏 O(n)（链状树）。

Q4：路径总和 III 为什么要回溯？

答：因为前缀和是路径相关的。当从一条路径切换到另一条路径时，之前路径上的前缀和不应该影响当前路径。回溯保证了前缀和只在当前路径上有效。

Q5：二叉搜索树的中序遍历有什么特殊性质？

答：BST 的中序遍历是递增序列。这个性质在很多 BST 题目中很关键，比如验证 BST、找第 K 小元素、二叉搜索树转有序链表等。

总结

二叉树题目的核心就一个字——递归。掌握递归的关键是：

  1. 明确递归函数的语义（这个函数返回什么？做什么事？）
  2. 正确处理 base case（通常是 node == null）
  3. 信任递归（假设子问题已经解决，只关注当前节点做什么）

二叉树重构类题目的通用思路：

  • 找到根节点（前序第一个 / 后序最后一个 / 层序第一个）
  • 在中序中定位根，分割出左右子树范围
  • 递归构建左右子树

一句话总结： 二叉树题型万变不离其宗——递归分治。理清递归函数的语义和 base case，90% 的二叉树题都能迎刃而解。

文档持续更新，欢迎打赏支持作者
Copyright © 2026 郑天祺