复盘 · LC 94 二叉树的中序遍历

题目

• 题号：LeetCode 94
• 名称：二叉树的中序遍历（Binary Tree Inorder Traversal）
• 难度：Easy
• 链接：leetcode.cn/problems/binary-tree-inorder-traversal
• 今日代码：94-二叉树的中序遍历/index.js

题意

给定二叉树根节点，返回中序遍历的节点值数组：左子树 → 根 → 右子树。

边界：空树 []、单节点、只有左链 / 只有右链。

涉及算法

标签	一句话
递归	左递归 → push(根) → 右递归
迭代 + 栈	一路向左压栈，弹出访问后再走右

教程对照：16 · 二叉树遍历。

评价我的解法

我的代码（摘自 94-二叉树的中序遍历/index.js，不含本地测例与 TreeNode 构造）：

function inorder(root, arr) {
  if (!root) {
    return;
  }
  inorder(root.left, arr);
  arr.push(root.val);
  inorder(root.right, arr);
}

var inorderTraversal = function (root) {
  const arr = [];
  inorder(root, arr);
  return arr;
};

干净、正确：辅助函数 + 结果数组是标准递归模板；空节点直接 return，边界稳。

• 时间 O(n)，空间 O(h)（递归栈，h 为高度；最坏链状 O(n)）。
• 优点：比链表日的「数组拆接」更贴近数据结构本意——按定义递归。
• 可补：面试常追问「不用递归、用栈怎么写」；知道即可。

最佳题解

递归版已是最佳之一。迭代栈版便于对照：

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  const res = [];
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop();
    res.push(cur.val);
    cur = cur.right;
  }
  return res;
};

• 时间 O(n)，空间 O(h)。
• 与递归等价：显式栈模拟「先钻左、再访问、再转右」。

关联题目

题	为何相关
144. 二叉树的前序遍历	同一套递归 / 栈，顺序改根左右
145. 二叉树的后序遍历	左右根；巩固三种遍历
98. 验证二叉搜索树	BST 中序应严格递增

一句话带走

中序：左 → 根 → 右；递归三行够用，栈版是「一路压左、弹出访问、再走右」。