[94] 二叉树的中序遍历

给定一个二叉树，返回它的 中序 遍历。

示例:

输入: [1,null,2,3]

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

非常典型的中序遍历树问题，有两种解法，递归与迭代。

递归法

递归写起来非常简单，遵循左-中-右的顺序即可。

function inorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  helper(root);
  return res;

  function helper(node: TreeNode | null) {
    if (!node) return;
    if (node.left) helper(node.left);
    res.push(node.val);
    if (node.right) helper(node.right);
  }
}

迭代法

迭代中序遍历利用了栈的特性。先将根节点入栈，指针指向根节点的左子节点，然后开始循环：

1. 指针节点所有左子节点全部依次入栈，
2. 取出栈顶节点，存储节点值，
3. 该节点若有右节点，指针指向其右节点。

直到节点栈空并且取出节点没有右子节点为止。

function inorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];

  const stack: TreeNode[] = [root];

  let cur = root.left;
  while (cur || stack.length > 0) {
    // 左子节点依次入栈
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    }
    // 读取并存储当前节点值
    cur = stack.pop();
    res.push(cur.val);
    // 指针指向右子节点
    cur = cur.right;
  }

  return res;
}

数的前中后序遍历方法相关题目：

[94] Binary Tree Inorder Traversal

[144] Binary Tree Preorder Traversal

[145] Binary Tree Postorder Traversal