手帐 Blog

主题

16 · 二叉树遍历 ​

目标：会写前序 / 中序 / 后序递归；会写层序 BFS；认识 TreeNode。

为什么面试会考 ​

前端面试树题几乎都从「遍历」出发：路径、深度、对称、层序打印……
遍历写不顺，后面经典题都会卡在「结点怎么走到」。

零基础概念 ​

js
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
}
遍历顺序（相对根）常见用途
前序根 → 左 → 右复制树、前缀表达
中序左 → 根 → 右BST 有序输出
后序左 → 右 → 根删树、算子树信息
层序一层一层BFS、按层收集

递归三问（每道树题都问自己）：

  1. 当前结点要做什么？
  2. 对左孩子递归什么？
  3. 对右孩子递归什么？空结点返回什么？

JS 模板：三种递归 + 层序 ​

js
function preorder(root, out = []) {
  if (!root) return out
  out.push(root.val)
  preorder(root.left, out)
  preorder(root.right, out)
  return out
}

function inorder(root, out = []) {
  if (!root) return out
  inorder(root.left, out)
  out.push(root.val)
  inorder(root.right, out)
  return out
}

function postorder(root, out = []) {
  if (!root) return out
  postorder(root.left, out)
  postorder(root.right, out)
  out.push(root.val)
  return out
}

function levelOrder(root) {
  if (!root) return []
  const res = []
  const q = [root]
  while (q.length) {
    const size = q.length
    const level = []
    for (let i = 0; i < size; i++) {
      const node = q.shift()
      level.push(node.val)
      if (node.left) q.push(node.left)
      if (node.right) q.push(node.right)
    }
    res.push(level)
  }
  return res
}

精讲题 ​

LeetCode 144. 二叉树的前序遍历 ​

js
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
  const res = []
  const dfs = (node) => {
    if (!node) return
    res.push(node.val)
    dfs(node.left)
    dfs(node.right)
  }
  dfs(root)
  return res
}

LeetCode 94. 二叉树的中序遍历 ​

js
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  const res = []
  const dfs = (node) => {
    if (!node) return
    dfs(node.left)
    res.push(node.val)
    dfs(node.right)
  }
  dfs(root)
  return res
}

迭代版（栈模拟，了解即可）：

js
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
}

LeetCode 102. 二叉树的层序遍历（入门） ​

见上方 levelOrder；提交版：

js
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return []
  const res = []
  const q = [root]
  while (q.length) {
    const size = q.length
    const level = []
    for (let i = 0; i < size; i++) {
      const node = q.shift()
      level.push(node.val)
      if (node.left) q.push(node.left)
      if (node.right) q.push(node.right)
    }
    res.push(level)
  }
  return res
}

注意：for 循环里固定本层 size，才能「一层一层」收集。

练习清单 ​

题提示
LeetCode 145. 二叉树的后序遍历左右根
LeetCode 589. N 叉树的前序遍历多孩子循环
LeetCode 107. 二叉树的层序遍历 II层序后 reverse，或头插
LeetCode 429. N 叉树的层序遍历同 BFS，孩子是数组

今日验收 ​

  • [ ] 三种递归遍历能默写
  • [ ] 层序能解释为何先存 size
  • [ ] 能画一棵 3 层小树手算前中后序结果

若你以前见过 ​

DOM 树、虚拟 DOM 的深度优先遍历，和二叉树 DFS 是同一套递归心智。