【算法刷题】二叉树前中后序遍历(递归+迭代)详解
🌈个人主页: Hygge_Code🔥热门专栏:从0开始学习Java | Linux学习| 计算机网络💫个人格言: “既然选择了远方，便不顾风雨兼程”
文章目录
一、二叉树的前序遍历🥝
1. 递归写法🍂
解题思路如下：
核心思路
前序遍历的规则是“根节点 → 左子树 → 右子树”，即先访问当前节点的值，再递归遍历左子树，最后递归遍历右子树。代码通过递归方式遵循这一规则，将遍历结果按顺序存储在列表中并返回。
步骤拆解
- 初始化存储结构：定义一个全局列表
list，用于按顺序存储前序遍历的节点值。 - 递归遍历函数
find：- 终止条件：若当前节点
node为null（空节点），则直接返回（无需处理）。 - 访问当前节点：若节点非空，将其值
node.val加入列表list（满足“根节点先访问”）。 - 递归左子树：调用
find(node.left)，继续遍历当前节点的左子树（遵循“左子树次之”）。 - 递归右子树：调用
find(node.right)，最后遍历当前节点的右子树（遵循“右子树最后”）。
- 终止条件：若当前节点
- 启动遍历并返回结果：在
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. 迭代写法🍂
采用迭代法（非递归），借助栈来模拟递归过程，解题思路如下：
核心思路
前序遍历的规则是“根节点 → 左子树 → 右子树”。迭代法通过栈存储待访问的节点，利用栈“先进后出”的特性，确保访问顺序符合前序规则：先访问当前节点，再优先处理左子树（后入栈），最后处理右子树（先入栈）。
步骤拆解
- 初始化：
- 定义列表
list用于存储遍历结果。 - 若根节点
root为空，直接返回空列表（边界处理）。 - 定义栈
stack（使用Deque实现，模拟栈的功能），并将根节点root入栈，作为遍历的起点。
- 定义列表
- 栈循环遍历：
- 当栈不为空时，循环执行以下操作：
- 弹出栈顶节点：获取当前待处理的节点
node。 - 访问当前节点：将节点值
node.val加入列表list（满足“根节点先访问”）。 - 右子树入栈：将当前节点的右子树
node.right入栈（右子树先入栈，会被后处理）。 - 左子树入栈：将当前节点的左子树
node.left入栈（左子树后入栈，会被先处理）。
- 弹出栈顶节点：获取当前待处理的节点
- 当栈不为空时，循环执行以下操作：
- 返回结果：当栈为空时，所有节点已遍历完毕，返回列表
list。
关键逻辑解析
- 栈的作用：替代递归中的调用栈，保存后续需要访问的节点。
- 入栈顺序：先右子树、后左子树。由于栈“先进后出”，左子树会先被弹出并访问，保证了“左子树在右子树之前”的前序规则。
示例说明
对于二叉树：
1 / \ 2 3 / \ 4 5 遍历过程：
- 栈初始：
[1]，弹出1→ 列表[1]，入栈右3、左2→ 栈变为[3, 2]。 - 弹出
2→ 列表[1,2]，入栈右5、左4→ 栈变为[3,5,4]。 - 弹出
4→ 列表[1,2,4]，无左右子树 → 栈变为[3,5]。 - 弹出
5→ 列表[1,2,4,5]，无左右子树 → 栈变为[3]。 - 弹出
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 节点时的结果。按照中序遍历规则，具体执行逻辑为：
- 先递归调用
inorder(root.left)，完整遍历root节点的左子树； - 待左子树遍历完成后，将当前
root节点的值加入结果集； - 最后递归调用
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);}}
迭代写法🍂
采用迭代法（非递归），借助栈来模拟递归过程，解题思路如下：
核心思路
中序遍历的规则是“左子树 → 根节点 → 右子树”。迭代法通过栈存储待访问的节点，利用栈“先进后出”的特性，先深入遍历左子树，再访问根节点，最后处理右子树，确保符合中序遍历顺序。
步骤拆解
- 初始化：
- 定义列表
list用于存储遍历结果。 - 若根节点
root为空，直接返回空列表（边界处理）。 - 定义栈
stack（使用Deque实现），用于暂存未访问的节点。
- 定义列表
- 栈循环遍历：
- 外层循环条件：
!stack.isEmpty() || root != null（栈非空或仍有节点待处理）。 - 左子树入栈：内层循环持续将当前节点
root及其左子树入栈（stack.push(root)），并移动到左子节点（root = root.left），直到左子树为空（root == null）。此时栈顶为左子树最深层的节点，符合“先左”的规则。 - 访问根节点：弹出栈顶节点（
root = stack.pop()），将其值加入列表list（此时左子树已遍历完毕，符合“再根”的规则）。 - 处理右子树：将
root指向当前节点的右子树（root = root.right），后续循环会按同样逻辑遍历右子树（符合“后右”的规则）。
- 外层循环条件：
- 返回结果：当栈为空且
root为null时，所有节点遍历完毕，返回列表list。
关键逻辑解析
- 栈的作用：保存“未访问根节点”，确保左子树遍历完成后能回溯到根节点。
- 内层循环：负责“一路向左”，将左子树所有节点入栈，保证左子树优先遍历。
- 出栈与右移：弹出根节点并访问后，转向右子树，重复左子树遍历逻辑，实现中序顺序。
示例说明
对于二叉树：
1 / \ 2 3 / \ 4 5 遍历过程：
- 初始
root=1，内层循环将1、2、4入栈 → 栈[1,2,4]，root变为null。 - 弹出
4→ 列表[4]，root指向4的右子树（null）。 - 栈非空，弹出
2→ 列表[4,2]，root指向2的右子树5。 - 内层循环将
5入栈 → 栈[1,5]，root变为null。 - 弹出
5→ 列表[4,2,5]，root指向5的右子树（null）。 - 栈非空，弹出
1→ 列表[4,2,5,1]，root指向1的右子树3。 - 内层循环将
3入栈 → 栈[3]，root变为null。 - 弹出
3→ 列表[4,2,5,1,3]，root指向3的右子树（null）。 - 栈空且
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 节点时的结果。按照后序遍历规则，执行逻辑为：
- 先递归调用
postorder(root.left)，完整遍历root节点的左子树； - 再递归调用
postorder(root.right)，遍历root节点的右子树； - 待左右子树均遍历完成后，将当前
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🍂🐦🔥
该代码通过迭代迭代法实现二叉树的后序遍历，核心思路是利用栈模拟递归过程，并通过标记已访问节点解决后序遍历中「左→右→根」的顺序问题。以下是详细解题思路：
关键难点👏👏👏
后序遍历的特殊顺序（根节点最后访问）导致单纯用栈难以直接区分「首次访问节点」和「左右子树已处理完毕的节点」。若不标记已访问的右子树，会导致右子树被重复处理或根节点提前访问。
解决方案
- 栈的作用：暂存尚未处理完左右子树的节点，确保能回溯到根节点。
- 标记已访问节点：用
pre指针记录上一个被访问的节点，通过判断「当前节点的右子树是否为空或已被访问」，确定是否可以访问当前根节点。
步骤拆解
- 初始化：创建结果列表
list、辅助栈stack，以及标记上一个访问节点的pre（初始为null）。 - 遍历左子树：
- 从当前节点
root出发，将所有左子树节点依次入栈，直到左子树为空（即root == null）。 - 这一步确保先处理完左子树，符合后序遍历的「左」优先原则。
- 从当前节点
- 处理栈顶节点：
- 取出栈顶节点
node（当前子树的根节点），检查其右子树状态：- 若右子树为空 或 右子树已被访问（
pre == node.right）：
说明左、右子树均已处理完毕，此时可以访问根节点node。将其值加入列表，弹出栈，并更新pre为node（标记为已访问），同时将root设为null（避免重复入栈左子树）。 - 若右子树未访问：
则需要先处理右子树，将root指向node.right，重复步骤 2 遍历右子树的左节点。
- 若右子树为空 或 右子树已被访问（
- 取出栈顶节点
- 循环终止条件：当
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 🍂🐦🔥
该代码通过前序遍历变形 + 列表翻转的技巧实现二叉树的后序遍历，以下是详细解题思路：
关键思路：前序与后序的转换关系🚀
观察遍历顺序的规律：
- 前序遍历顺序为 根 → 左 → 右。
- 后序遍历顺序为 左 → 右 → 根。
如果将前序遍历的顺序调整为 根 → 右 → 左（即先访问右子树，再访问左子树），得到的结果恰好是后序遍历的逆序。因此，只需：
- 先按「根 → 右 → 左」的顺序遍历并记录节点值。（借鉴前序遍历迭代写法的思路）
- 最后将记录的列表翻转，即可得到「左 → 右 → 根」的后序遍历结果。
步骤拆解
- 初始化：创建结果列表
list和辅助栈stack，若根节点为空直接返回空列表。 - 按「根 → 右 → 左」顺序遍历：
- 将根节点入栈，开启循环（栈不为空时持续处理）。
- 弹出栈顶节点
node，将其值加入列表（先访问「根」）。 - 若
node有左子树，将左子树入栈（后续会被右子树之后处理，确保「右 → 左」的顺序）。 - 若
node有右子树，将右子树入栈（右子树先入栈会被先弹出，即先访问「右」）。 - 重复上述过程，直到栈为空，此时列表中记录的顺序为「根 → 右 → 左」。
- 翻转列表得到后序遍历：
- 使用
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;}}如果我的内容对你有帮助，请 点赞 ， 评论 ， 收藏 。创作不易，大家的支持就是我坚持下去的动力！
