二叉树深度指南

面向前端/全栈工程师的二叉树完整攻略：原理讲解 → ASCII 图解 → 完整可运行代码 → 复杂度分析 → 面试实战
涵盖二叉树基础、四种遍历、DFS/BFS、BST 操作、LeetCode 经典高频题

一、二叉树基础

1.1 节点定义（TreeNode）

typescript

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null

  constructor(val: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val
    this.left = left ?? null
    this.right = right ?? null
  }
}

javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

1.2 二叉树分类

满二叉树（Full / Perfect Binary Tree）

每层节点数都达到最大值，深度为 k 的满二叉树有 2^k - 1 个节点。

           1
         /   \
        2     3
       / \   / \
      4   5 6   7

特征：所有叶子节点在同一层，每个非叶子节点都有两个子节点。

完全二叉树（Complete Binary Tree）

除最后一层外，每层节点数都达到最大值，最后一层节点从左到右连续排列。

特征：可以用数组高效存储，父子关系通过下标计算——父节点 i，左子 2i+1，右子 2i+2。

二叉搜索树（Binary Search Tree / BST）

对于任意节点，左子树所有节点值 < 当前节点值 < 右子树所有节点值。

           8
         /   \
        3     10
       / \      \
      1   6     14
         / \   /
        4   7 13

特征：中序遍历结果为升序序列。平均查找时间复杂度 O(log n)，最差退化为链表 O(n)。

平衡二叉树（AVL Tree）

任意节点的左右子树高度差不超过 1 的二叉搜索树。

    平衡 AVL                 不平衡
        4                      1
       / \                      \
      2   6                      2
     / \ / \                      \
    1  3 5  7                      3

特征：通过旋转操作保持平衡，保证查找/插入/删除均为 O(log n)。

二、四种遍历

以下面这棵树为例：

2.1 前序遍历（LeetCode 144）

顺序：根 → 左 → 右

访问顺序：1 → 2 → 4 → 5 → 3 → 6

        1 ①
       / \
    ② 2   3 ⑤
     / \   \
  ③ 4   5④  6 ⑥

递归实现

typescript

function preorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = []

  function dfs(node: TreeNode | null) {
    if (!node) return
    result.push(node.val)
    dfs(node.left)
    dfs(node.right)
  }

  dfs(root)
  return result
}

迭代实现（栈）

typescript

function preorderTraversal(root: TreeNode | null): number[] {
  if (!root) return []
  const result: number[] = []
  const stack: TreeNode[] = [root]

  while (stack.length) {
    const node = stack.pop()!
    result.push(node.val)
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  }

  return result
}

复杂度：时间 O(n)，空间 O(n)

2.2 中序遍历（LeetCode 94）

顺序：左 → 根 → 右

访问顺序：4 → 2 → 5 → 1 → 3 → 6

        1 ④
       / \
    ② 2   3 ⑤
     / \   \
  ① 4   5③  6 ⑥

递归实现

typescript

function inorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = []

  function dfs(node: TreeNode | null) {
    if (!node) return
    dfs(node.left)
    result.push(node.val)
    dfs(node.right)
  }

  dfs(root)
  return result
}

迭代实现（栈）

typescript

function inorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = []
  const stack: TreeNode[] = []
  let curr: TreeNode | null = root

  while (curr || stack.length) {
    while (curr) {
      stack.push(curr)
      curr = curr.left
    }
    curr = stack.pop()!
    result.push(curr.val)
    curr = curr.right
  }

  return result
}

复杂度：时间 O(n)，空间 O(n)

2.3 后序遍历（LeetCode 145）

顺序：左 → 右 → 根

访问顺序：4 → 5 → 2 → 6 → 3 → 1

        1 ⑥
       / \
    ③ 2   3 ⑤
     / \   \
  ① 4   5②  6 ④

递归实现

typescript

function postorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = []

  function dfs(node: TreeNode | null) {
    if (!node) return
    dfs(node.left)
    dfs(node.right)
    result.push(node.val)
  }

  dfs(root)
  return result
}

迭代实现（栈 + 反转）

typescript

function postorderTraversal(root: TreeNode | null): number[] {
  if (!root) return []
  const result: number[] = []
  const stack: TreeNode[] = [root]

  while (stack.length) {
    const node = stack.pop()!
    result.push(node.val)
    if (node.left) stack.push(node.left)
    if (node.right) stack.push(node.right)
  }

  return result.reverse()
}

复杂度：时间 O(n)，空间 O(n)

2.4 层序遍历（LeetCode 102）

顺序：逐层从左到右

访问顺序：[1] → [2, 3] → [4, 5, 6]

  第 0 层    1
           / \
  第 1 层  2   3
          / \   \
  第 2 层 4   5   6

递归实现（DFS 按层收集）

typescript

function levelOrder(root: TreeNode | null): number[][] {
  const result: number[][] = []

  function dfs(node: TreeNode | null, depth: number) {
    if (!node) return
    if (result.length === depth) result.push([])
    result[depth].push(node.val)
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)
  }

  dfs(root, 0)
  return result
}

迭代实现（队列 BFS）

typescript

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return []
  const result: number[][] = []
  const queue: TreeNode[] = [root]

  while (queue.length) {
    const size = queue.length
    const level: number[] = []

    for (let i = 0; i < size; i++) {
      const node = queue.shift()!
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

复杂度：时间 O(n)，空间 O(n)

三、DFS vs BFS

3.1 对比表

维度	DFS（深度优先）	BFS（广度优先）
数据结构	栈（递归调用栈 / 显式栈）	队列
空间复杂度	O(h)，h 为树高	O(w)，w 为最大层宽
最坏空间	O(n) 退化链表	O(n) 完全二叉树最后一层 ≈ n/2
适用场景	路径问题、回溯、拓扑排序	最短路径、层级遍历、逐层处理
实现难度	递归简洁，迭代稍复杂	迭代直观
探索方式	一条路走到底再回溯	逐层扩展

3.2 DFS 代码模板

typescript

function dfs(root: TreeNode | null): void {
  if (!root) return

  // 前序位置：进入节点时处理
  dfs(root.left)
  // 中序位置：左子树处理完后
  dfs(root.right)
  // 后序位置：离开节点时处理
}

3.3 BFS 代码模板

typescript

function bfs(root: TreeNode | null): void {
  if (!root) return
  const queue: TreeNode[] = [root]

  while (queue.length) {
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }
}

3.4 图示对比

DFS 探索路径（前序）            BFS 探索路径
        1                          1
       ↙                         ↙   ↘
      2    ↗  3                 2      3
     ↙  ↗     ↘              ↙  ↘      ↘
    4   5       6            4    5      6

  1→2→4→(回)→5→(回)→3→6     1→2→3→4→5→6

四、二叉搜索树 BST

4.1 搜索

查找值 6：

        8              8 > 6 → 左
       / \
      3   10           3 < 6 → 右
     / \    \
    1   6   14         6 = 6 → 找到！
       / \
      4   7

typescript

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  if (!root || root.val === val) return root
  return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val)
}

复杂度：时间 O(h)，空间 O(h)，h 为树高

4.2 插入

插入值 5：

        8              8 > 5 → 左
       / \
      3   10           3 < 5 → 右
     / \    \
    1   6   14         6 > 5 → 左
       / \
      4   7            4 < 5 → 右，插入！
       \
        5  ← 新节点

typescript

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
  if (!root) return new TreeNode(val)
  if (val < root.val) root.left = insertIntoBST(root.left, val)
  else root.right = insertIntoBST(root.right, val)
  return root
}

复杂度：时间 O(h)，空间 O(h)

4.3 删除

删除节点有三种情况：

情况一：叶子节点 — 直接删除

删除 4：
        8                 8
       / \               / \
      3   10     →      3   10
     / \    \          / \    \
    1   4   14        1  null  14

情况二：只有一个子节点 — 用子节点替代

删除 10：
        8                 8
       / \               / \
      3   10     →      3   14
     / \    \          / \
    1   6   14        1   6

情况三：有两个子节点 — 用右子树最小值（中序后继）替代

删除 3：
        8                 8
       / \               / \
      3   10     →      4   10
     / \    \          / \    \
    1   6   14        1   6   14
       / \               / \
      4   7             null  7

步骤：找到右子树最小值 4 → 用 4 替换 3 → 删除原来的 4

typescript

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (!root) return null

  if (key < root.val) {
    root.left = deleteNode(root.left, key)
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key)
  } else {
    if (!root.left) return root.right
    if (!root.right) return root.left

    let minNode = root.right
    while (minNode.left) {
      minNode = minNode.left
    }
    root.val = minNode.val
    root.right = deleteNode(root.right, minNode.val)
  }

  return root
}

复杂度：时间 O(h)，空间 O(h)

4.4 验证 BST（LeetCode 98）

利用 BST 中序遍历为升序的性质，也可以用上下界递归。

typescript

function isValidBST(root: TreeNode | null): boolean {
  function validate(node: TreeNode | null, min: number, max: number): boolean {
    if (!node) return true
    if (node.val <= min || node.val >= max) return false
    return validate(node.left, min, node.val) && validate(node.right, node.val, max)
  }

  return validate(root, -Infinity, Infinity)
}

复杂度：时间 O(n)，空间 O(n)

五、经典题目完整实现

5.1 二叉树的最大深度（LeetCode 104）

思路分析

树的最大深度 = max(左子树深度, 右子树深度) + 1。递归到空节点返回 0。

ASCII 图解

        3            深度计算过程：
       / \
      9   20         depth(3) = max(depth(9), depth(20)) + 1
         / \                  = max(1, 2) + 1 = 3
        15   7
                     depth(9)  = max(0, 0) + 1 = 1
                     depth(20) = max(depth(15), depth(7)) + 1
                              = max(1, 1) + 1 = 2

完整代码

typescript

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

BFS 解法：

typescript

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0
  const queue: TreeNode[] = [root]
  let depth = 0

  while (queue.length) {
    const size = queue.length
    depth++
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }

  return depth
}

复杂度：时间 O(n)，空间 O(n)（最差退化链表），平均 O(log n)

5.2 翻转二叉树（LeetCode 226）

思路分析

递归地交换每个节点的左右子树。前序或后序位置交换均可。

ASCII 图解

     翻转前              翻转后
        4                  4
       / \                / \
      2   7      →       7   2
     / \ / \            / \ / \
    1  3 6  9          9  6 3  1

完整代码

typescript

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null
  const temp = root.left
  root.left = root.right
  root.right = temp
  invertTree(root.left)
  invertTree(root.right)
  return root
}

复杂度：时间 O(n)，空间 O(n)

5.3 对称二叉树（LeetCode 101）

思路分析

判断一棵树是否关于根节点轴对称。等价于判断左子树和右子树是否互为镜像：左子树的左 = 右子树的右，左子树的右 = 右子树的左。

ASCII 图解

     对称二叉树                非对称
         1                      1
        / \                    / \
       2   2                  2   2
      / \ / \                  \   \
     3  4 4  3                  3    3

  比较路径：                 右子的左为 null ≠ 左子的右 null
  L.left(3) == R.right(3) ✓     不满足镜像
  L.right(4) == R.left(4) ✓

完整代码

typescript

function isSymmetric(root: TreeNode | null): boolean {
  function isMirror(l: TreeNode | null, r: TreeNode | null): boolean {
    if (!l && !r) return true
    if (!l || !r) return false
    return l.val === r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left)
  }

  return isMirror(root?.left ?? null, root?.right ?? null)
}

复杂度：时间 O(n)，空间 O(n)

5.4 从前序与中序遍历序列构造二叉树（LeetCode 105）

思路分析

前序遍历的第一个元素是根节点。在中序遍历中找到根节点位置，左边是左子树，右边是右子树。递归构建。

ASCII 图解

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

第 1 步：根 = 3
         中序中 3 的位置 = 1
         左子树中序 = [9]      左子树前序 = [9]
         右子树中序 = [15,20,7] 右子树前序 = [20,15,7]

第 2 步：左子树根 = 9（叶子）   右子树根 = 20
                               中序中 20 位置 → 左[15] 右[7]

结果：
        3
       / \
      9   20
         / \
        15   7

完整代码

typescript

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const map = new Map<number, number>()
  inorder.forEach((val, idx) => map.set(val, idx))

  function build(preStart: number, preEnd: number, inStart: number, inEnd: number): TreeNode | null {
    if (preStart > preEnd) return null

    const rootVal = preorder[preStart]
    const root = new TreeNode(rootVal)
    const inRoot = map.get(rootVal)!
    const leftSize = inRoot - inStart

    root.left = build(preStart + 1, preStart + leftSize, inStart, inRoot - 1)
    root.right = build(preStart + leftSize + 1, preEnd, inRoot + 1, inEnd)

    return root
  }

  return build(0, preorder.length - 1, 0, inorder.length - 1)
}

复杂度：时间 O(n)，空间 O(n)（哈希表 + 递归栈）

5.5 最近公共祖先 LCA（LeetCode 236）

思路分析

对于节点 p 和 q，它们的最近公共祖先满足：p 和 q 分别位于该节点的左右子树中（或该节点本身就是 p 或 q）。递归地在左右子树中查找，根据返回值判断。

ASCII 图解

        3
       / \
      5   1          查找 LCA(5, 1)
     / \ / \
    6  2 0  8        左子树找到 5，右子树找到 1
      / \            → 当前节点 3 就是 LCA
     7   4

        3
       / \
      5   1          查找 LCA(5, 4)
     / \ / \
    6  2 0  8        左子树：5 本身是目标，且 4 在 5 的子树中
      / \            → LCA 是 5
     7   4

完整代码

typescript

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  if (!root || root === p || root === q) return root

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left && right) return root
  return left ?? right
}

复杂度：时间 O(n)，空间 O(n)

5.6 二叉树的直径（LeetCode 543）

思路分析

二叉树的直径 = 任意两节点之间路径的最大长度（边数）。经过某节点的最长路径 = 左子树深度 + 右子树深度。在求深度的过程中顺便更新全局最大值。

ASCII 图解

        1
       / \
      2   3          经过节点 2 的路径：
     / \               左深度 = 1 (→4)
    4   5              右深度 = 1 (→5)
                       路径长度 = 1 + 1 = 2

                     经过节点 1 的路径：
                       左深度 = 2 (1→2→4 或 1→2→5)
                       右深度 = 1 (1→3)
                       路径长度 = 2 + 1 = 3 ← 最大直径

完整代码

typescript

function diameterOfBinaryTree(root: TreeNode | null): number {
  let maxDiameter = 0

  function depth(node: TreeNode | null): number {
    if (!node) return 0
    const left = depth(node.left)
    const right = depth(node.right)
    maxDiameter = Math.max(maxDiameter, left + right)
    return Math.max(left, right) + 1
  }

  depth(root)
  return maxDiameter
}

复杂度：时间 O(n)，空间 O(n)

六、面试题（5 道详细解答）

面试题 1：序列化与反序列化二叉树（LeetCode 297）

设计一个算法，将二叉树序列化为字符串，并能从字符串反序列化还原二叉树。

思路分析

使用前序遍历序列化，用特殊标记 "#" 表示空节点。反序列化时按前序顺序递归重建。

ASCII 图解

        1
       / \
      2   3          序列化 → "1,2,#,#,3,4,#,#,5,#,#"
         / \
        4   5        反序列化过程：
                     取 1 → 根
                     取 2 → 左子 → 取 # → 左空 → 取 # → 右空
                     取 3 → 右子 → 取 4 → ... → 取 5 → ...

完整代码

typescript

function serialize(root: TreeNode | null): string {
  if (!root) return '#'
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`
}

function deserialize(data: string): TreeNode | null {
  const vals = data.split(',')
  let index = 0

  function build(): TreeNode | null {
    const val = vals[index++]
    if (val === '#') return null
    const node = new TreeNode(Number(val))
    node.left = build()
    node.right = build()
    return node
  }

  return build()
}

复杂度：时间 O(n)，空间 O(n)

面试题 2：二叉树的右视图（LeetCode 199）

给定一棵二叉树，返回从右侧所能看到的节点值。

思路分析

BFS 层序遍历，每层取最后一个节点；或 DFS 优先访问右子树，每层第一个访问的就是右视图节点。

ASCII 图解

        1        ← 看到 1
       / \
      2   3      ← 看到 3
       \   \
        5   4    ← 看到 4

右视图结果：[1, 3, 4]

完整代码

typescript

function rightSideView(root: TreeNode | null): number[] {
  if (!root) return []
  const result: number[] = []
  const queue: TreeNode[] = [root]

  while (queue.length) {
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!
      if (i === size - 1) result.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }

  return result
}

DFS 解法：

typescript

function rightSideView(root: TreeNode | null): number[] {
  const result: number[] = []

  function dfs(node: TreeNode | null, depth: number) {
    if (!node) return
    if (depth === result.length) result.push(node.val)
    dfs(node.right, depth + 1)
    dfs(node.left, depth + 1)
  }

  dfs(root, 0)
  return result
}

复杂度：时间 O(n)，空间 O(n)

面试题 3：二叉树展开为链表（LeetCode 114）

给定一棵二叉树，将其原地展开为单链表（按前序遍历顺序，全部挂在右子树上）。

思路分析

后序遍历思路：先递归展开左右子树，然后把左子树插入到右子树的位置，原右子树接到左子树末尾。

ASCII 图解

        1              1              1
       / \              \              \
      2   5     →       2       →      2
     / \   \             \              \
    3   4   6             3              3
                           \              \
                            4              4
                             \              \
                              5              5
                               \              \
                                6              6

完整代码

typescript

function flatten(root: TreeNode | null): void {
  if (!root) return

  flatten(root.left)
  flatten(root.right)

  const left = root.left
  const right = root.right

  root.left = null
  root.right = left

  let p: TreeNode = root
  while (p.right) {
    p = p.right
  }
  p.right = right
}

复杂度：时间 O(n)，空间 O(n)

面试题 4：路径总和 III（LeetCode 437）

给定一棵二叉树和一个目标和 targetSum，找出路径和等于 targetSum 的路径数量。路径不需要从根节点开始，也不需要在叶子节点结束，但方向必须向下。

思路分析

使用前缀和 + 哈希表。记录从根到当前节点的路径前缀和，如果 当前前缀和 - targetSum 在哈希表中出现过，说明存在一段子路径和为 targetSum。

ASCII 图解

        10
       /  \
      5   -3         targetSum = 8
     / \    \
    3   2   11       路径：
   / \   \             10 → 5 → 3 = 18? 否
  3  -2   1             5 → 3 = 8 ✓
                        10 → -3 → 11 = 18? 否
前缀和过程：              -3 → 11 = 8 ✓
节点 10: sum=10, 10-8=2 不在 map           5 → 2 → 1 = 8 ✓
节点 5:  sum=15, 15-8=7 不在 map
节点 3:  sum=18, 18-8=10 在 map! count++   共 3 条路径

完整代码

typescript

function pathSum(root: TreeNode | null, targetSum: number): number {
  const prefixMap = new Map<number, number>()
  prefixMap.set(0, 1)
  let count = 0

  function dfs(node: TreeNode | null, currSum: number) {
    if (!node) return

    currSum += node.val
    count += prefixMap.get(currSum - targetSum) ?? 0
    prefixMap.set(currSum, (prefixMap.get(currSum) ?? 0) + 1)

    dfs(node.left, currSum)
    dfs(node.right, currSum)

    prefixMap.set(currSum, prefixMap.get(currSum)! - 1)
  }

  dfs(root, 0)
  return count
}

复杂度：时间 O(n)，空间 O(n)

面试题 5：二叉树中的最大路径和（LeetCode 124）

给定一棵二叉树，找出节点值之和最大的路径。路径可以从任意节点开始到任意节点结束（不一定经过根节点），但路径中不能重复经过同一节点。

思路分析

对于每个节点，经过它的最大路径和 = 左子树的最大贡献 + 节点值 + 右子树的最大贡献。而对上层节点的贡献只能选左或右中较大的一条。负贡献取 0（不选该子树）。

ASCII 图解

       -10
       /  \
      9    20         经过 20 的路径：15 → 20 → 7 = 42
          / \
         15   7       经过 -10 的路径：9 + (-10) + 20+max(15,7) = 9-10+35 = 34

                      节点 15 贡献：15    节点 7 贡献：7
                      节点 20 路径和：15+20+7 = 42 → 全局最大
                      节点 20 对上层贡献：20+max(15,7) = 35
                      节点 -10 路径和：9+(-10)+35 = 34 < 42

                      最大路径和 = 42

完整代码

typescript

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity

  function maxGain(node: TreeNode | null): number {
    if (!node) return 0

    const left = Math.max(maxGain(node.left), 0)
    const right = Math.max(maxGain(node.right), 0)

    maxSum = Math.max(maxSum, node.val + left + right)

    return node.val + Math.max(left, right)
  }

  maxGain(root)
  return maxSum
}

复杂度：时间 O(n)，空间 O(n)

七、追问思考（5 道）

深入思考

Morris 遍历：如何在 O(1) 额外空间内完成中序遍历？Morris 遍历利用线索（Threaded）指针的原理是什么？在什么场景下值得使用？
BST 第 K 小元素（LeetCode 230）：如果 BST 被频繁修改（插入/删除），如何优化第 K 小元素的查找？能否在每个节点维护子树大小来实现 O(h) 查找？
二叉树的序列化压缩：LeetCode 297 的序列化字符串可能很长，有哪些方法可以压缩序列化结果？层序遍历 vs 前序遍历哪种方式产生的字符串更短？
红黑树 vs AVL 树：两者都是自平衡 BST，红黑树在工程实践中（如 Java TreeMap、Linux 内核 CFS 调度器）为何更受欢迎？旋转次数、平衡条件、适用场景有何差异？
从递归到迭代的通用转换：能否用一个统一的栈模拟框架实现前序、中序、后序遍历？标记法（给已访问节点打标记）的核心思路是什么？

二叉树深度指南 ​

一、二叉树基础 ​

1.1 节点定义（TreeNode） ​

1.2 二叉树分类 ​

满二叉树（Full / Perfect Binary Tree） ​

完全二叉树（Complete Binary Tree） ​

二叉搜索树（Binary Search Tree / BST） ​

平衡二叉树（AVL Tree） ​

二、四种遍历 ​

2.1 前序遍历（LeetCode 144） ​

递归实现 ​

迭代实现（栈） ​

2.2 中序遍历（LeetCode 94） ​

递归实现 ​

迭代实现（栈） ​

2.3 后序遍历（LeetCode 145） ​

递归实现 ​

迭代实现（栈 + 反转） ​

2.4 层序遍历（LeetCode 102） ​

递归实现（DFS 按层收集） ​

迭代实现（队列 BFS） ​

三、DFS vs BFS ​

3.1 对比表 ​

3.2 DFS 代码模板 ​

3.3 BFS 代码模板 ​

3.4 图示对比 ​

四、二叉搜索树 BST ​

4.1 搜索 ​

4.2 插入 ​

4.3 删除 ​

情况一：叶子节点 — 直接删除 ​

情况二：只有一个子节点 — 用子节点替代 ​

情况三：有两个子节点 — 用右子树最小值（中序后继）替代 ​

4.4 验证 BST（LeetCode 98） ​

五、经典题目完整实现 ​

5.1 二叉树的最大深度（LeetCode 104） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

5.2 翻转二叉树（LeetCode 226） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

5.3 对称二叉树（LeetCode 101） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

5.4 从前序与中序遍历序列构造二叉树（LeetCode 105） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

5.5 最近公共祖先 LCA（LeetCode 236） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

5.6 二叉树的直径（LeetCode 543） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

六、面试题（5 道详细解答） ​

面试题 1：序列化与反序列化二叉树（LeetCode 297） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

面试题 2：二叉树的右视图（LeetCode 199） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

面试题 3：二叉树展开为链表（LeetCode 114） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

面试题 4：路径总和 III（LeetCode 437） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

面试题 5：二叉树中的最大路径和（LeetCode 124） ​

思路分析 ​

ASCII 图解 ​

完整代码 ​

二叉树深度指南

一、二叉树基础

1.1 节点定义（TreeNode）

1.2 二叉树分类

满二叉树（Full / Perfect Binary Tree）

完全二叉树（Complete Binary Tree）

二叉搜索树（Binary Search Tree / BST）

平衡二叉树（AVL Tree）

二、四种遍历

2.1 前序遍历（LeetCode 144）

递归实现

迭代实现（栈）

2.2 中序遍历（LeetCode 94）

递归实现

迭代实现（栈）

2.3 后序遍历（LeetCode 145）

递归实现

迭代实现（栈 + 反转）

2.4 层序遍历（LeetCode 102）

递归实现（DFS 按层收集）

迭代实现（队列 BFS）

三、DFS vs BFS

3.1 对比表

3.2 DFS 代码模板

3.3 BFS 代码模板

3.4 图示对比

四、二叉搜索树 BST

4.1 搜索

4.2 插入

4.3 删除

情况一：叶子节点 — 直接删除

情况二：只有一个子节点 — 用子节点替代

情况三：有两个子节点 — 用右子树最小值（中序后继）替代

4.4 验证 BST（LeetCode 98）

五、经典题目完整实现

5.1 二叉树的最大深度（LeetCode 104）

思路分析

ASCII 图解

完整代码

5.2 翻转二叉树（LeetCode 226）

思路分析

ASCII 图解

完整代码

5.3 对称二叉树（LeetCode 101）

思路分析

ASCII 图解

完整代码

5.4 从前序与中序遍历序列构造二叉树（LeetCode 105）

思路分析

ASCII 图解

完整代码

5.5 最近公共祖先 LCA（LeetCode 236）

思路分析

ASCII 图解

完整代码

5.6 二叉树的直径（LeetCode 543）

思路分析

ASCII 图解

完整代码

六、面试题（5 道详细解答）

面试题 1：序列化与反序列化二叉树（LeetCode 297）

思路分析

ASCII 图解

完整代码

面试题 2：二叉树的右视图（LeetCode 199）

思路分析

ASCII 图解

完整代码

面试题 3：二叉树展开为链表（LeetCode 114）

思路分析

ASCII 图解

完整代码

面试题 4：路径总和 III（LeetCode 437）

思路分析

ASCII 图解

完整代码

面试题 5：二叉树中的最大路径和（LeetCode 124）

思路分析

ASCII 图解

完整代码