手帐 Blog

主题

18 · BFS 层序与 BST ​

目标：层序遍历写熟；会 BST 搜索与校验；说清 BST 中序有序。

为什么面试会考 ​

  • BFS：图/树最短层数、按层输出、锯齿层序都靠队列。
  • BST：很多「有序」性质能 O(log n) 搜索；校验 BST 是高频易错题（只比左右孩子不够）。

零基础概念 ​

BST（二叉搜索树）：任意结点，左子树都 < 它，右子树都 > 它（题面可能允许相等，以题为准）。

中序遍历 BST → 得到非递减序列。

校验时每个结点要落在合法区间 (min, max) 内，不只和父结点比。

JS 模板：BST 区间校验 ​

js
function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true
  if (root.val <= min || root.val >= max) return false
  return (
    isValidBST(root.left, min, root.val) &&
    isValidBST(root.right, root.val, max)
  )
}

精讲题 ​

LeetCode 102. 二叉树的层序遍历 ​

（巩固；若 16 已做过可当复习默写）

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
}

LeetCode 700. 二叉搜索树中的搜索 ​

js
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
  let cur = root
  while (cur) {
    if (cur.val === val) return cur
    cur = val < cur.val ? cur.left : cur.right
  }
  return null
}

也可递归：val < root.val 搜左，否则搜右。

LeetCode 98. 验证二叉搜索树 ​

js
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  const dfs = (node, min, max) => {
    if (!node) return true
    if (node.val <= min || node.val >= max) return false
    return dfs(node.left, min, node.val) && dfs(node.right, node.val, max)
  }
  return dfs(root, -Infinity, Infinity)
}

易错：只判断 left.val < root.val < right.val，忽略更深层——必须带区间。

练习清单 ​

题提示
LeetCode 199. 二叉树的右视图层序取每层最后一个
LeetCode 103. 二叉树的锯齿形层序遍历奇数层 reverse
LeetCode 701. 二叉搜索树中的插入操作找空位挂上
LeetCode 230. 二叉搜索树中第 K 小的元素中序第 k 个

今日验收 ​

  • [ ] 102 默写含 size 的层序
  • [ ] 700 迭代搜索一遍过
  • [ ] 98 能指出「只比父子」为什么错

若你以前见过 ​

前端路由树、文件系统目录，BFS「按层」和「优先浅层」的产品逻辑常能对上号。