.jpg)
804 字
4 分钟
二叉树的中序遍历
.png)
题目描述
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
解题思路
- 递归法：
- 先递归遍历左子树
- 访问根节点值
- 再递归遍历右子树
- 迭代法：
- 使用栈模拟递归过程
- 沿左子树深入到底部并入栈
- 弹出栈顶节点访问后转向右子树
- Morris遍历：
- 利用空闲指针实现无栈遍历
- 建立临时链接指向中序前驱
- 遍历结束恢复树结构
- 统一迭代法：
- 使用标记法处理节点访问顺序
- 显式控制栈中节点的访问状态
关键洞察
- 访问顺序特性：
- 左子树→根节点→右子树
- 天然递归结构
- 栈模拟核心：
- 深入左链到底再回溯
- 右子树视为新子树处理
- 空间优化本质：
- Morris利用叶子节点空指针
- 临时构造中序线索二叉树
- 状态标记优势：
- 统一模板解决三种遍历
- 避免复杂条件判断
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 优势 |
|---|---|---|---|
| 递归 | O(n) | O(h) | 代码简洁直观 |
| 迭代 | O(n) | O(h) | 避免递归栈溢出风险 |
| Morris遍历 | O(n) | O(1) | 常数空间复杂度 |
| 统一迭代法 | O(n) | O(h) | 三种遍历使用统一模板 |
代码实现
递归法
const inorderRecursive = (root) => { const res = []; const dfs = (node) => { if (!node) return; dfs(node.left); res.push(node.val); dfs(node.right); }; dfs(root); return res;};迭代法
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function (root) { const result = []; const stack = []; let current = root; while (current || stack.length) { while (current) { stack.push(current); current = current.left; } current = stack.pop(); result.push(current.val); current = current.right; } return result;};Mirrors
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[]} */const inorderTraversal = (root) => { const res = []; let cur = root; while (cur) { if (!cur.left) { // 无左子树直接访问 res.push(cur.val); cur = cur.right; } else { // 寻找前驱节点 let pre = cur.left; while (pre.right && pre.right !== cur) { pre = pre.right; }
if (!pre.right) { // 建立线索 pre.right = cur; cur = cur.left; } else { // 断开线索 pre.right = null; res.push(cur.val); cur = cur.right; } } } return res;};实际应用场景
- 表达式求值：中序遍历表达式树得到中缀表达式`
- 二叉搜索树：中序遍历BST得到有序序列`
- 数据库索引：B+树的中序遍历实现范围查询`
- 编译器构建：抽象语法树的中序遍历生成中间代码“