94. 二叉树的中序遍历

题目描述

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

示例 1：

输入：root = [1,null,2,3]

输出：[1,3,2]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

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

出处：LeetCode

解法一：递归

思路

递归遍历二叉树，先遍历左子树，再遍历根节点，最后遍历右子树。

实现

function inorderTraversal(root: TreeNode | null): number[] {
  const res: number[] = [];
  inorder(root, res);
  return res;
}

function inorder(root: TreeNode | null, res: number[]): void {
  if (root === null) {
    return;
  }
  inorder(root.left, res);
  res.push(root.val);
  inorder(root.right, res);
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数。递归函数 inorder 遍历所有节点。
• 空间复杂度：$O(n)$。空间复杂度取决于递归的栈空间。

解法二：迭代

思路

使用栈模拟递归的过程，先遍历左子树，再遍历根节点，最后遍历右子树。

实现

function inorderTraversal(root: TreeNode | null): number[] {
  const res: number[] = [];
  const stack: TreeNode[] = [];
  let cur = root;
  while (cur !== null || stack.length > 0) {
    while (cur !== null) {
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop()!;
    res.push(cur.val);
    cur = cur.right;
  }
  return res;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数。迭代的过程中，每个节点会被访问一次。
• 空间复杂度：$O(n)$。空间复杂度取决于栈的空间。

解法三：Morris 遍历

思路

Morris 遍历是一种遍历二叉树的方法，可以实现 $O(1)$ 的空间复杂度。

Morris 遍历的思路是利用线索二叉树，线索二叉树是在二叉树的空指针上保存前驱或后继节点的指针，这样可以在遍历的过程中不需要额外的空间。

实现

function inorderTraversal(root: TreeNode | null): number[] {
  const res: number[] = [];
  let cur = root;
  while (cur !== null) {
    if (cur.left === null) {
      res.push(cur.val);
      cur = cur.right;
    } else {
      let pre = cur.left;
      while (pre.right !== null && pre.right !== cur) {
        pre = pre.right;
      }
      if (pre.right === null) {
        pre.right = cur;
        cur = cur.left;
      } else {
        pre.right = null;
        res.push(cur.val);
        cur = cur.right;
      }
    }
  }
  return res;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数。Morris 遍历的过程中，每个节点会被访问两次。
• 空间复杂度：$O(1)$。Morris 遍历只需要常数的空间。