2022-04-29.md

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

信息卡片

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

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例1：

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

示例2：

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

示例3：

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

示例4：

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

示例5：

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

提示：

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

思路分析

1. 递归 → 1

参考答案

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

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

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

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

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

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

3. Morris 遍历（待补充）

核心思想是利用树的大量空闲指针，实现空间开销的极限缩减