前序中序后序遍历解题方法_二叉树遍历全攻略

什么是二叉树遍历？

在数据结构与算法中，二叉树遍历是指按照某种特定的次序访问二叉树中的每个节点，使得每个节点被访问一次且仅被访问一次。由于二叉树是非线性结构，每个节点都可能有两个子节点，因此遍历过程需要将非线性结构线性化。

常见的遍历方式主要有三种：前序遍历（Pre-order）、中序遍历（In-order）和后序遍历（Post-order）。这三种遍历方式的核心区别在于访问根节点（Root）、左子树（Left）和右子树（Right）的相对顺序。掌握这三种遍历方法是解决二叉树相关问题的基石，也是LeetCode算法题中的绝对高频考点。

前序遍历 (DLR)

根->左->右。首先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。常用于复制树结构或序列化。

中序遍历 (LDR)

左->根->右。首先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。对于二叉搜索树（BST），中序遍历结果为有序序列。

后序遍历 (LRD)

左->右->根。首先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。常用于删除树结构或计算目录大小。

前序中序后序遍历解题方法详解

解决遍历问题的方法主要分为两大类：递归法和迭代法（非递归）。递归法代码简洁，易于理解，但可能面临栈溢出的风险；迭代法则需要显式使用栈（Stack）或队列（Queue）来模拟递归过程，是面试中的进阶考点。

递归法原理与实现

递归法是解决树问题最直观的方法。其核心思想是将大问题分解为小问题：遍历一棵树等同于遍历其左子树和右子树。

1. 前序遍历 (Pre-order)

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    result.add(root.val);          // 1. 访问根
    result.addAll(preorderTraversal(root.left));  // 2. 遍历左
    result.addAll(preorderTraversal(root.right)); // 3. 遍历右
    return result;
}
                

2. 中序遍历 (In-order)

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    result.addAll(inorderTraversal(root.left));   // 1. 遍历左
    result.add(root.val);                         // 2. 访问根
    result.addAll(inorderTraversal(root.right));  // 3. 遍历右
    return result;
}
                

3. 后序遍历 (Post-order)

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    result.addAll(postorderTraversal(root.left)); // 1. 遍历左
    result.addAll(postorderTraversal(root.right)); // 2. 遍历右
    result.add(root.val);                         // 3. 访问根
    return result;
}
                

💡 记忆技巧：根节点的位置决定了遍历的名称。根在前是前序，根在中是中序，根在后是后序。

迭代法原理与实现

迭代法需要使用栈（Stack）来模拟递归调用栈的行为。对于前序遍历，由于根节点最先访问，我们可以直接将根节点压栈，然后依次处理右子节点和左子节点（因为栈是后进先出，所以右子节点要先压栈，左子节点后压栈，这样出栈时左子节点先被处理）。

1. 前序遍历迭代实现

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

2. 中序遍历迭代实现

中序遍历的迭代实现稍复杂，因为根节点需要在左子树遍历完之后才访问。我们需要一直向左走，将路径上的节点压栈，直到左子节点为空，然后弹出栈顶节点访问，再转向其右子树。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    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;
}
                

3. 后序遍历迭代实现

后序遍历的迭代实现可以通过修改前序遍历的策略来完成。我们知道前序是“根->左->右”，如果我们改为“根->右->左”，然后将结果反转，就得到了“左->右->根”，即后序遍历。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.left != null) stack.push(node.left);   // 左子节点先入栈
        if (node.right != null) stack.push(node.right); // 右子节点后入栈
    }
    Collections.reverse(result); // 反转结果
    return result;
}
                

Morris遍历（空间复杂度O(1)）

Morris遍历是一种利用叶子节点的空指针来存储临时信息，从而实现非递归且非栈的遍历方法。其核心思想是利用中序前驱节点。

时间复杂度：O(N)，每个节点最多被访问两次。
空间复杂度：O(1)，不需要栈或递归调用栈。
适用场景：对空间复杂度有极致要求的场景，但会修改树的结构（遍历后恢复）。

由于Morris遍历逻辑较为复杂，且在实际面试中考察频率低于前两种方法，此处仅提供思路说明。核心步骤包括：找到当前节点左子树的最右节点（前驱），如果前驱右指针为空，则将其指向当前节点并进入左子树；如果前驱右指针已指向当前节点，则说明左子树已遍历完，恢复指针，访问当前节点并进入右子树。

LeetCode 真题深度解析

理解遍历方法只是第一步，如何在实际问题中应用这些方法才是关键。以下精选了三道经典真题，分别对应前序+中序建树、中序+后序建树以及路径总和问题。

案例一：从前序与中序遍历序列构造二叉树 (LeetCode 105)

题目描述：给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解题思路：

确定根节点：前序遍历的第一个元素一定是当前子树的根节点。
划分左右子树：在中序遍历中找到根节点的位置，根节点左侧为左子树的中序遍历，右侧为右子树的中序遍历。
确定子树范围：根据左子树的节点数量，可以在前序遍历中确定左子树和右子树的前序遍历范围。
递归构建：对左子树和右子树递归执行上述步骤。

代码示例：

public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 使用HashMap加速查找中序遍历中的根节点位置
    Map<Integer, Integer> indexMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        indexMap.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, indexMap);
}
private TreeNode build(int[] preorder, int preStart, int preEnd,
                       int[] inorder, int inStart, int inEnd,
                       Map<Integer, Integer> indexMap) {
    if (preStart > preEnd || inStart > inEnd) return null;
    // 前序遍历的第一个节点是根节点
    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);
    // 在中序遍历中找到根节点的位置
    int inRoot = indexMap.get(rootVal);
    // 左子树的节点数量
    int leftSubtreeSize = inRoot - inStart;
    // 递归构建左子树和右子树
    root.left = build(preorder, preStart + 1, preStart + leftSubtreeSize,
                      inorder, inStart, inRoot - 1, indexMap);
    root.right = build(preorder, preStart + leftSubtreeSize + 1, preEnd,
                       inorder, inRoot + 1, inEnd, indexMap);
    return root;
}
                

⚡ 关键点：前序遍历确定根，中序遍历划分左右。两者结合可以唯一确定一棵二叉树（前提是树中无重复值）。

案例二：从中序与后序遍历序列构造二叉树 (LeetCode 106)

核心区别：与案例一类似，但后序遍历的最后一个元素是根节点。划分左右子树的逻辑相同，只是前序遍历变成了后序遍历，且根节点在序列的末尾。

解题步骤：

后序遍历的最后一个元素是根。
在中序中找到根，划分左右子树。
根据左子树大小，在后序中确定左子树和右子树的范围。

案例三：路径总和 (LeetCode 112)

题目描述：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

解题思路：

这是一个典型的前序遍历应用场景。我们可以使用深度优先搜索（DFS），从根节点开始，不断减去当前节点的值，直到叶子节点，判断剩余值是否为0。

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}
                

网友们还关心：前序中序后序遍历解题方法周边知识

在深入学习了基本的遍历方法后，许多学习者往往会遇到一些进阶问题或相关概念混淆的情况。以下是基于搜索引擎数据和社区讨论整理的热门周边知识，旨在帮助您构建更完整的知识体系。

1. 层序遍历（BFS）与DFS的区别

前序、中序、后序都属于深度优先搜索（DFS），它们沿着树的深度遍历树的节点，尽可能深地搜索树的分支。而层序遍历（Level Order Traversal）属于广度优先搜索（BFS），它从根节点开始，沿着树的宽度遍历树的节点。

特性	DFS (前/中/后序)	BFS (层序)
数据结构	栈 (Stack)	队列 (Queue)
访问顺序	纵向深入	横向逐层
空间复杂度	O(H), H为树高	O(W), W为最大宽度
典型应用	路径查找、建树	最短路径、层级处理

2. 为什么前序+中序可以唯一确定一棵树，而前序+后序不行？

这是一个非常经典的面试题。

前序+中序：前序确定了根节点，中序确定了根节点的左右子树划分。这种“根+左右划分”的组合是唯一的，因此可以唯一确定二叉树。
前序+后序：前序确定了根，后序也确定了根，但无法确定左右子树的边界。例如，前序[1,2]和后序[2,1]，根是1，但2可以是左孩子也可以是右孩子。因此，仅凭前序和后序无法唯一确定一棵二叉树，除非树是满二叉树或每个节点都有0或2个子节点。

前序中序后序遍历解题方法常见问题 (FAQ)

Q1: 前序遍历和中序遍历能否唯一确定一棵二叉树？

是的，只要树中节点的值不重复，前序遍历和中序遍历可以唯一确定一棵二叉树。前序遍历的第一个元素是根节点，在中序遍历中找到该根节点，其左侧为左子树，右侧为右子树。递归地应用此过程即可重建整棵树。

Q2: 为什么中序遍历对于二叉搜索树（BST）很重要？

对于二叉搜索树（BST），其定义是左子树所有节点值小于根节点，右子树所有节点值大于根节点。因此，对BST进行中序遍历（左-根-右），得到的序列一定是一个升序排列的有序序列。这一性质常用于验证二叉树是否为BST，或从有序数组构建平衡BST。

Q3: 在Java中，如何实现非递归的前序遍历？

非递归前序遍历可以使用 `java.util.Stack`。将根节点压入栈中。当栈不为空时，弹出栈顶节点并访问它。然后，先将右子节点压入栈（如果存在），再将左子节点压入栈（如果存在）。这样可以保证左子节点先被处理，符合前序遍历“根-左-右”的顺序。

Q4: 后序遍历的非递归实现为什么比前序和中序复杂？

因为在后序遍历中，根节点是在左右子树都处理完之后才访问的。在迭代过程中，当我们从栈中弹出一个节点时，我们需要知道它的左右子树是否都已经访问过。因此，通常需要额外的指针（如 `prev`）来记录上一个访问的节点，或者使用两个栈来实现。相比之下，前序和中序在访问根节点时，其子树的处理状态是明确的。

掌握遍历，征服二叉树

前序、中序、后序遍历是二叉树操作的基石。无论是递归还是迭代，理解其背后的逻辑比死记硬背代码更重要。建议读者结合LeetCode真题，手动模拟遍历过程，逐步加深理解。希望本文的 前序中序后序遍历解题方法 能为您在算法学习的道路上提供有力的支持。