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

Ne0inhk

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

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

在这里插入图片描述

文章目录

一、二叉树的前序遍历🥝

在这里插入图片描述

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

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

在这里插入图片描述

Read more

最新电子电气架构（EEA）调研-3

而新一代的强实时性、高确定性，以及满足CAP定理的同步分布式协同技术（SDCT），可以实现替代TSN、DDS的应用，且此技术已经在无人车辆得到验证，同时其低成本学习曲线、无复杂二次开发工作，将开发人员的劳动强度、学习曲线极大降低，使开发人员更多的去完成算法、执行器功能完善。 五、各大车厂的EEA 我们调研策略是从公开信息中获得各大车厂的EEA信息，并在如下中进行展示。 我们集中了华为、特斯拉、大众、蔚来、小鹏、理想、东风（岚图）等有代表领先性的车辆电子电气架构厂商。        1、华为 图12 华为的CCA电子电气架构              （1）华为“计算＋通信”CC架构的三个平台                         1）MDC智能驾驶平台；                         2）CDC智能座舱平台                         3）VDC整车控制平台。        联接指的是华为智能网联解决方案，解决车内、车外网络高速连接问题，云服务则是基于云计算提供的服务，如在线车主服务、娱乐和OTA等。 华

By Ne0inhk
Apache IoTDB 架构特性与 Prometheus+Grafana 监控体系部署实践

Apache IoTDB 架构特性与 Prometheus+Grafana 监控体系部署实践

Apache IoTDB 架构特性与 Prometheus+Grafana 监控体系部署实践 文章目录 * Apache IoTDB 架构特性与 Prometheus+Grafana 监控体系部署实践 * Apache IoTDB 核心特性与价值 * Apache IoTDB 监控面板完整部署方案 * 安装步骤 * 步骤一：IoTDB开启监控指标采集 * 步骤二：安装、配置Prometheus * 步骤三：安装grafana并配置数据源 * 步骤四：导入IoTDB Grafana看板 * TimechoDB（基于 Apache IoTDB）增强特性 * 总结与应用场景建议 Apache IoTDB 核心特性与价值 Apache IoTDB 专为物联网场景打造的高性能轻量级时序数据库，以 “设备 - 测点” 原生数据模型贴合物理设备与传感器关系，通过高压缩算法、百万级并发写入能力和毫秒级查询响应优化海量时序数据存储成本与处理效率，同时支持边缘轻量部署、

By Ne0inhk
SQL Server 2019安装教程(超详细图文)

SQL Server 2019安装教程(超详细图文)

SQL Server 介绍） SQL Server 是由 微软（Microsoft） 开发的一款 关系型数据库管理系统（RDBMS），支持结构化查询语言（SQL）进行数据存储、管理和分析。自1989年首次发布以来，SQL Server 已成为企业级数据管理的核心解决方案，广泛应用于金融、电商、ERP、CRM 等业务系统。它提供高可用性、安全性、事务处理（ACID）和商业智能（BI）支持，并支持 Windows 和 Linux 跨平台部署。 一、获取 SQL Server 2019 安装包 1. 官方下载方式 前往微软官网注册账号后，即可下载 SQL Server Developer 版本（

By Ne0inhk