【算法刷题】二叉树前中后序遍历(递归+迭代)详解

🌈个人主页: Hygge_Code🔥热门专栏:从0开始学习Java | Linux学习| 计算机网络💫个人格言: “既然选择了远方，便不顾风雨兼程”

文章目录

• 一、二叉树的前序遍历🥝
  • 1. 递归写法🍂
    • 核心思路
    • 步骤拆解
    • 示例说明
    • 代码🍋‍🟩
  • 2. 迭代写法🍂
    • 核心思路
    • 步骤拆解
    • 关键逻辑解析
    • 示例说明
    • 代码🍋‍🟩
• 二、二叉树的中序遍历🥝
  • 1. 递归写法🍂
    • 思路
    • 代码🍋‍🟩
  • 迭代写法🍂
    • 核心思路
    • 步骤拆解
    • 关键逻辑解析
    • 示例说明
    • 代码🍋‍🟩
• 三、二叉树的后序遍历🥝
  • 递归写法🍂
    • 思路
    • 代码🍋‍🟩
  • 迭代写法1🍂🐦‍🔥
    • 关键难点👏👏👏
    • 解决方案
    • 步骤拆解
    • 示例流程
    • 代码🍋‍🟩
  • 迭代写法2 🍂🐦‍🔥
    • 关键思路：前序与后序的转换关系🚀
    • 步骤拆解
    • 示例流程
    • 代码🍋‍🟩

一、二叉树的前序遍历🥝

1. 递归写法🍂

解题思路如下：

核心思路

前序遍历的规则是“根节点 → 左子树 → 右子树”，即先访问当前节点的值，再递归遍历左子树，最后递归遍历右子树。代码通过递归方式遵循这一规则，将遍历结果按顺序存储在列表中并返回。

步骤拆解

1. 初始化存储结构：定义一个全局列表 list，用于按顺序存储前序遍历的节点值。
2. 递归遍历函数 find：
   • 终止条件：若当前节点 node 为 null（空节点），则直接返回（无需处理）。
   • 访问当前节点：若节点非空，将其值 node.val 加入列表 list（满足“根节点先访问”）。
   • 递归左子树：调用 find(node.left)，继续遍历当前节点的左子树（遵循“左子树次之”）。
   • 递归右子树：调用 find(node.right)，最后遍历当前节点的右子树（遵循“右子树最后”）。
3. 启动遍历并返回结果：在 preorderTraversal 方法中，以根节点 root 为起点调用 find 函数，触发整个树的遍历，最终返回存储结果的列表 list。

示例说明

对于一棵简单二叉树：

 1 \ 2 / 3 

遍历过程为：

• 访问根节点 1 → 列表为 [1]；
• 递归右子树（左子树为空），访问节点 2 → 列表为 [1,2]；
• 递归节点 2 的左子树，访问节点 3 → 列表为 [1,2,3]；
• 所有节点遍历完成，返回 [1,2,3]，符合前序遍历规则。

通过递归自然贴合前序遍历的定义，代码简洁且易于理解，时间复杂度为 O(n)（n 为节点数，每个节点访问一次），空间复杂度为 O(n)（递归栈深度最坏为 n，列表存储需 n 空间）。

代码🍋‍🟩

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{privateList<Integer> list =newArrayList<>();publicList<Integer>preorderTraversal(TreeNode root){find(root);return list;}privatevoidfind(TreeNode node){if(node !=null){ list.add(node.val);find(node.left);find(node.right);}}}

2. 迭代写法🍂

采用迭代法（非递归），借助栈来模拟递归过程，解题思路如下：

核心思路

前序遍历的规则是“根节点 → 左子树 → 右子树”。迭代法通过栈存储待访问的节点，利用栈“先进后出”的特性，确保访问顺序符合前序规则：先访问当前节点，再优先处理左子树（后入栈），最后处理右子树（先入栈）。

步骤拆解

1. 初始化：
   • 定义列表 list 用于存储遍历结果。
   • 若根节点 root 为空，直接返回空列表（边界处理）。
   • 定义栈 stack（使用 Deque 实现，模拟栈的功能），并将根节点 root 入栈，作为遍历的起点。
2. 栈循环遍历：
   • 当栈不为空时，循环执行以下操作：
     • 弹出栈顶节点：获取当前待处理的节点 node。
     • 访问当前节点：将节点值 node.val 加入列表 list（满足“根节点先访问”）。
     • 右子树入栈：将当前节点的右子树 node.right 入栈（右子树先入栈，会被后处理）。
     • 左子树入栈：将当前节点的左子树 node.left 入栈（左子树后入栈，会被先处理）。
3. 返回结果：当栈为空时，所有节点已遍历完毕，返回列表 list。

关键逻辑解析

• 栈的作用：替代递归中的调用栈，保存后续需要访问的节点。
• 入栈顺序：先右子树、后左子树。由于栈“先进后出”，左子树会先被弹出并访问，保证了“左子树在右子树之前”的前序规则。

示例说明

对于二叉树：

 1 / \ 2 3 / \ 4 5 

遍历过程：

1. 栈初始：[1]，弹出 1 → 列表 [1]，入栈右 3、左 2 → 栈变为 [3, 2]。
2. 弹出 2 → 列表 [1,2]，入栈右 5、左 4 → 栈变为 [3,5,4]。
3. 弹出 4 → 列表 [1,2,4]，无左右子树 → 栈变为 [3,5]。
4. 弹出 5 → 列表 [1,2,4,5]，无左右子树 → 栈变为 [3]。
5. 弹出 3 → 列表 [1,2,4,5,3]，无左右子树 → 栈空，遍历结束。

最终结果 [1,2,4,5,3] 符合前序遍历规则。

迭代避免了递归可能的栈溢出问题，时间复杂度为 O(n)（每个节点入栈、出栈各一次），空间复杂度为 O(n)（栈的最大深度取决于树的高度，最坏为 n）。

代码🍋‍🟩

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicList<Integer>preorderTraversal(TreeNode root){List<Integer> list =newArrayList<Integer>();if(root ==null)return list;Deque<TreeNode> stack =newLinkedList<TreeNode>(); stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.peek(); stack.pop();if(node ==null)continue; list.add(node.val); stack.push(node.right); stack.push(node.left);}return list;}}

二、二叉树的中序遍历🥝

1. 递归写法🍂

思路

二叉树的中序遍历遵循“左子树——根节点——右子树”的访问顺序，这一过程可通过递归函数直观模拟。

定义函数 inorder(root) 用于返回遍历到 root 节点时的结果。按照中序遍历规则，具体执行逻辑为：

1. 先递归调用 inorder(root.left)，完整遍历 root 节点的左子树；
2. 待左子树遍历完成后，将当前 root 节点的值加入结果集；
3. 最后递归调用 inorder(root.right)，遍历 root 节点的右子树。

当遇到空节点（root 为 null）时，递归终止（无需执行任何操作）。

通过这种层层递归的方式，自然贴合中序遍历“先左、再根、后右”的顺序，最终可得到整棵树的中序遍历结果。

代码🍋‍🟩

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicList<Integer>inorderTraversal(TreeNode root){List<Integer> list =newArrayList<Integer>();if(root==null)return list;inOrder(root,list);return list;}publicvoidinOrder(TreeNode root,List<Integer>list){if(root ==null)return;inOrder(root.left,list); list.add(root.val);inOrder(root.right,list);}}

迭代写法🍂

采用迭代法（非递归），借助栈来模拟递归过程，解题思路如下：

核心思路

中序遍历的规则是“左子树 → 根节点 → 右子树”。迭代法通过栈存储待访问的节点，利用栈“先进后出”的特性，先深入遍历左子树，再访问根节点，最后处理右子树，确保符合中序遍历顺序。

步骤拆解

1. 初始化：
   • 定义列表 list 用于存储遍历结果。
   • 若根节点 root 为空，直接返回空列表（边界处理）。
   • 定义栈 stack（使用 Deque 实现），用于暂存未访问的节点。
2. 栈循环遍历：
   • 外层循环条件：!stack.isEmpty() || root != null（栈非空或仍有节点待处理）。
   • 左子树入栈：内层循环持续将当前节点 root 及其左子树入栈（stack.push(root)），并移动到左子节点（root = root.left），直到左子树为空（root == null）。此时栈顶为左子树最深层的节点，符合“先左”的规则。
   • 访问根节点：弹出栈顶节点（root = stack.pop()），将其值加入列表 list（此时左子树已遍历完毕，符合“再根”的规则）。
   • 处理右子树：将 root 指向当前节点的右子树（root = root.right），后续循环会按同样逻辑遍历右子树（符合“后右”的规则）。
3. 返回结果：当栈为空且 root 为 null 时，所有节点遍历完毕，返回列表 list。

关键逻辑解析

• 栈的作用：保存“未访问根节点”，确保左子树遍历完成后能回溯到根节点。
• 内层循环：负责“一路向左”，将左子树所有节点入栈，保证左子树优先遍历。
• 出栈与右移：弹出根节点并访问后，转向右子树，重复左子树遍历逻辑，实现中序顺序。

示例说明

对于二叉树：

 1 / \ 2 3 / \ 4 5 

遍历过程：

1. 初始 root=1，内层循环将 1、2、4 入栈 → 栈 [1,2,4]，root 变为 null。
2. 弹出 4 → 列表 [4]，root 指向 4 的右子树（null）。
3. 栈非空，弹出 2 → 列表 [4,2]，root 指向 2 的右子树 5。
4. 内层循环将 5 入栈 → 栈 [1,5]，root 变为 null。
5. 弹出 5 → 列表 [4,2,5]，root 指向 5 的右子树（null）。
6. 栈非空，弹出 1 → 列表 [4,2,5,1]，root 指向 1 的右子树 3。
7. 内层循环将 3 入栈 → 栈 [3]，root 变为 null。
8. 弹出 3 → 列表 [4,2,5,1,3]，root 指向 3 的右子树（null）。
9. 栈空且 root 为 null，遍历结束。

最终结果 [4,2,5,1,3] 符合中序遍历规则。

该思路通过迭代高效实现中序遍历，时间复杂度为 O(n)（每个节点入栈、出栈各一次），空间复杂度为 O(n)（栈的最大深度取决于树的高度，最坏为 n）。

代码🍋‍🟩

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicList<Integer>inorderTraversal(TreeNode root){List<Integer> list =newArrayList<Integer>();if(root ==null)return list;Deque<TreeNode> stack =newLinkedList<TreeNode>();while(!stack.isEmpty()|| root !=null){while(root !=null){ stack.push(root); root = root.left;} root = stack.pop(); list.add(root.val); root = root.right;}return list;}}

三、二叉树的后序遍历🥝

递归写法🍂

思路

二叉树的后序遍历遵循“左子树——右子树——根节点”的访问顺序，可通过递归函数模拟：

定义函数 postorder(root) 用于返回遍历到 root 节点时的结果。按照后序遍历规则，执行逻辑为：

1. 先递归调用 postorder(root.left)，完整遍历 root 节点的左子树；
2. 再递归调用 postorder(root.right)，遍历 root 节点的右子树；
3. 待左右子树均遍历完成后，将当前 root 节点的值加入结果集。

当遇到空节点（root 为 null）时，递归终止（无需执行任何操作）。

通过这种层层递归的方式，自然贴合后序遍历“先左、再右、最后根”的顺序，最终可得到整棵树的后序遍历结果。

代码🍋‍🟩

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicList<Integer>postorderTraversal(TreeNode root){List<Integer> list =newArrayList<Integer>();if(root ==null)return list;postOrder(root,list);return list;}publicvoidpostOrder(TreeNode root,List<Integer> list){if(root ==null)return;postOrder(root.left,list);postOrder(root.right,list); list.add(root.val);}}

迭代写法1🍂🐦‍🔥

该代码通过迭代迭代法实现二叉树的后序遍历，核心思路是利用栈模拟递归过程，并通过标记已访问节点解决后序遍历中「左→右→根」的顺序问题。以下是详细解题思路：

关键难点👏👏👏

后序遍历的特殊顺序（根节点最后访问）导致单纯用栈难以直接区分「首次访问节点」和「左右子树已处理完毕的节点」。若不标记已访问的右子树，会导致右子树被重复处理或根节点提前访问。

解决方案

1. 栈的作用：暂存尚未处理完左右子树的节点，确保能回溯到根节点。
2. 标记已访问节点：用 pre 指针记录上一个被访问的节点，通过判断「当前节点的右子树是否为空或已被访问」，确定是否可以访问当前根节点。

步骤拆解

1. 初始化：创建结果列表 list、辅助栈 stack，以及标记上一个访问节点的 pre（初始为 null）。
2. 遍历左子树：
   • 从当前节点 root 出发，将所有左子树节点依次入栈，直到左子树为空（即 root == null）。
   • 这一步确保先处理完左子树，符合后序遍历的「左」优先原则。
3. 处理栈顶节点：
   • 取出栈顶节点 node（当前子树的根节点），检查其右子树状态：
     • 若右子树为空 或 右子树已被访问（pre == node.right）：
       说明左、右子树均已处理完毕，此时可以访问根节点 node。将其值加入列表，弹出栈，并更新 pre 为 node（标记为已访问），同时将 root 设为 null（避免重复入栈左子树）。
     • 若右子树未访问：
       则需要先处理右子树，将 root 指向 node.right，重复步骤 2 遍历右子树的左节点。
4. 循环终止条件：当 root 为空且栈为空时，所有节点处理完毕，返回结果列表。

示例流程

以二叉树 1 -> 2（左）-> 3（右） 为例（结构：1 是根，左孩子 2，2 的右孩子 3）：

• 初始 root=1，入栈 1 → 入栈 2（左子树）→ 入栈 3（左子树为空，处理栈顶 3）。
• 3 的右子树为空，加入列表 [3]，弹出 3，pre=3，root=null。
• 栈顶为 2，右子树 3 已访问（pre=3），加入列表 [3,2]，弹出 2，pre=2，root=null。
• 栈顶为 1，右子树为空，加入列表 [3,2,1]，弹出 1，栈空，循环结束。

代码🍋‍🟩

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicList<Integer>postorderTraversal(TreeNode root){List<Integer> list =newArrayList<Integer>();if(root ==null)return list;Deque<TreeNode>stack =newLinkedList<TreeNode>();TreeNode pre =null;// 记录上一个访问的结点(凭这个来判断是否访问过右子树)while(root !=null||!stack.isEmpty()){while(root !=null){ stack.push(root); root = root.left;}TreeNode node = stack.peek();// 若右子树为空或已访问过，则弹出并记录当前节点if(node.right ==null|| pre == node.right){ list.add(stack.pop().val); pre = node; root =null;// 避免重复入栈左子树}else{ root = node.right;}}return list;}}

迭代写法2 🍂🐦‍🔥

该代码通过前序遍历变形 + 列表翻转的技巧实现二叉树的后序遍历，以下是详细解题思路：

关键思路：前序与后序的转换关系🚀

观察遍历顺序的规律：

• 前序遍历顺序为 根 → 左 → 右。
• 后序遍历顺序为 左 → 右 → 根。

如果将前序遍历的顺序调整为 根 → 右 → 左（即先访问右子树，再访问左子树），得到的结果恰好是后序遍历的逆序。因此，只需：

1. 先按「根 → 右 → 左」的顺序遍历并记录节点值。（借鉴前序遍历迭代写法的思路）
2. 最后将记录的列表翻转，即可得到「左 → 右 → 根」的后序遍历结果。

步骤拆解

1. 初始化：创建结果列表 list 和辅助栈 stack，若根节点为空直接返回空列表。
2. 按「根 → 右 → 左」顺序遍历：
   • 将根节点入栈，开启循环（栈不为空时持续处理）。
   • 弹出栈顶节点 node，将其值加入列表（先访问「根」）。
   • 若 node 有左子树，将左子树入栈（后续会被右子树之后处理，确保「右 → 左」的顺序）。
   • 若 node 有右子树，将右子树入栈（右子树先入栈会被先弹出，即先访问「右」）。
   • 重复上述过程，直到栈为空，此时列表中记录的顺序为「根 → 右 → 左」。
3. 翻转列表得到后序遍历：
   • 使用 Collections.reverse(list) 翻转列表，将「根 → 右 → 左」转换为「左 → 右 → 根」，即后序遍历结果。

示例流程

以二叉树 1（根）→ 2（左）→ 3（右）（结构：1 的左孩子是 2，2 的右孩子是 3）为例：

• 初始栈：[1]，弹出 1 加入列表 → list = [1]。
• 入栈 1 的左孩子 2 → 栈：[2]；再入栈 1 的右孩子（为空，忽略）。
• 弹出 2 加入列表 → list = [1,2]；入栈 2 的左孩子（为空），再入栈 2 的右孩子 3 → 栈：[3]。
• 弹出 3 加入列表 → list = [1,2,3]；3 无左右孩子，栈为空。
• 翻转列表 → [3,2,1]，即后序遍历结果。

代码🍋‍🟩

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicList<Integer>postorderTraversal(TreeNode root){List<Integer> list =newArrayList<Integer>();if(root ==null)return list;Deque<TreeNode>stack =newLinkedList<TreeNode>(); stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop(); list.add(node.val);if(node.left !=null) stack.push(node.left);if(node.right !=null) stack.push(node.right);}Collections.reverse(list);return list;}}

如果我的内容对你有帮助，请 点赞 ， 评论 ， 收藏 。创作不易，大家的支持就是我坚持下去的动力！