2022-04-28.md

每日一题 - 二叉树的中序遍历

信息卡片

• 时间：2022-04-28
• 题目链接：https://leetcode.com/problems/binary-tree-inorder-traversal/
• tag：栈 树 深度优先搜索 二叉树

题目描述

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

示例1：

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

示例2：

输入：root = []
输出：[]

示例3：

输入：root = [1]
输出：[1]

提示：

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

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

思路分析

1. 利用递归 → 1
2. 循环遍历解答往往是考核的目的
3. 利用栈把根节点压入（往往是经过，不访问，所以利用栈存放）
4. 根节点的左子树访问结束，再弹出根节点访问 → 2

参考答案

1. 递归 $O(n)$

空间复杂度：$O(n)$

/**
 * 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)
 * }
 */
function inorderTraversal(root) {
  let res = []
  if (!root) return res
  // 左子树
  res = [
    ...res,
    ...inorderTraversal(root.left)
  ]
  // 当前根节点
  res.push(root.val)
  // 右子树
  res = [
    ...res,
    ...inorderTraversal(root.right)
  ]
  return res
}

2. 循环遍历 $O(n)$

1. 当前节点压入栈
2. 访问其左子树（一直向下访问直到无左子树）
3. 弹出栈顶并记录值
4. 访问其右子树 → 1.（循环）

function inorderTraversal(root) {
  let res = []
  let stack = []

  // 栈不为空 或者 当前节点存在
  while(root || stack.length) {
    while(root) {
      // 当前根节点不为空，压入栈
      stack.push(root)
      // 访问当前根节点左子树
      root = root.left
    }
    // ↑循环完后：最左边叶子节点在栈顶（第一次）

    // 弹出栈顶节点
    root = stack.pop()
    // 弹出的节点值放入结果中
    res.push(root.val)
    // 访问弹出节点的右子树
    // 如果没有：root = null（用于 while 循环判断）
    root = root.right
  }
  return res
}