算法——二叉树总结

发表于 分类于 ， ， ， 阅读次数：

二叉树是最常见的数据结构之一，很多复杂问题（二叉搜索树、堆、Trie）都是在二叉树基础上扩展的。本文总结二叉树的核心操作和常见题型。

二叉树的遍历

  遍历是二叉树最基本的操作，分为深度优先（DFS）和广度优先（BFS）两大类。

前序遍历（Preorder）：根 → 左 → 右

1
2
3
4
function preorder(root) {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

中序遍历（Inorder）：左 → 根 → 右

1
2
3
4
function inorder(root) {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

  中序遍历二叉搜索树（BST）会得到一个有序序列，这是一个很重要的性质。

后序遍历（Postorder）：左 → 右 → 根

1
2
3
4
function postorder(root) {
  if (!root) return [];
  return [...postorder(root.left), ...postorder(root.right), root.val];
}

层序遍历（Level Order）：逐层从左到右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const len = queue.length;
    const level = [];
    for (let i = 0; i < len; 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;
}

DFS（Depth-First Search）

  DFS 指的是「一路走到头再回头」的搜索方式，二叉树的前序、中序、后序遍历都是 DFS 的具体形态。区别在于访问根节点的时机。

1
2
3
4
5
6
7
8
9
// DFS 通用模板（递归）
function dfs(node) {
  if (!node) return;
  // 前序位置
  dfs(node.left);
  // 中序位置
  dfs(node.right);
  // 后序位置
}

  DFS 也可以写成非递归（用栈模拟），核心思想是手动维护一个栈来模拟系统调用栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 前序非递归：根 → 左 → 右
// 每弹出一个节点就访问，然后先压右子节点再压左子节点
function preorderIterative(root) {
  if (!root) return [];
  const stack = [root];
  const result = [];
  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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 中序非递归：左 → 根 → 右
// 先一路把左子节点压栈，到底后弹出访问，再处理右子树
function inorderIterative(root) {
  const stack = [];
  const result = [];
  let node = root;
  while (stack.length || node) {
    // 一路向左压栈
    while (node) {
      stack.push(node);
      node = node.left;
    }
    // 弹出访问
    node = stack.pop();
    result.push(node.val);
    // 转向右子树
    node = node.right;
  }
  return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 后序非递归：左 → 右 → 根
// 技巧：按 根 → 右 → 左 遍历后反转结果 = 左 → 右 → 根
function postorderIterative(root) {
  if (!root) return [];
  const stack = [root];
  const result = [];
  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();
}

  三种非递归遍历总结：

遍历方式 栈用法 核心思路
前序 根压栈 → 弹出访问 → 右左压栈 右先入栈，左后出
中序 一路左压栈 → 弹出 → 转向右 用 while 走到底再回头
后序 根压栈 → 弹出记录 → 左右压栈 → 反转 前序变体 + reverse

BFS（Breadth-First Search）

  BFS 是「一层一层扫」的搜索方式，对应二叉树的层序遍历。BFS 通常用队列实现。

  BFS 有两个常见变体：

  • 逐层输出：上面 levelOrder 的例子，每一层一个数组
  • 求最短路径：BFS 首次到达目标节点时走过的路径一定最短
1
2
3
4
5
6
7
8
9
10
11
// BFS 求二叉树最小深度
function minDepth(root) {
  if (!root) return 0;
  const queue = [[root, 1]];
  while (queue.length) {
    const [node, depth] = queue.shift();
    if (!node.left && !node.right) return depth;
    if (node.left) queue.push([node.left, depth + 1]);
    if (node.right) queue.push([node.right, depth + 1]);
  }
}

序列化与反序列化

  序列化是把二叉树转换成字符串（或数组），反序列化是把字符串还原回二叉树。主要用于数据传输和缓存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 前序序列化
function serialize(root) {
  if (!root) return '#';
  return root.val + ',' + serialize(root.left) + ',' + serialize(root.right);
}

// 前序反序列化
function deserialize(str) {
  const list = str.split(',');
  function build() {
    const val = list.shift();
    if (val === '#') return null;
    const node = new TreeNode(Number(val));
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

  也可以用层序遍历做序列化，结果更直观：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 层序序列化
function serializeLevel(root) {
  if (!root) return '[]';
  const queue = [root];
  const result = [];
  while (queue.length) {
    const node = queue.shift();
    if (node) {
      result.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    } else {
      result.push('#');
    }
  }
  // 去掉尾部多余的 '#'
  while (result[result.length - 1] === '#') result.pop();
  return JSON.stringify(result);
}

二叉树与链表的关系

  二叉树和链表有很深的联系：

  1. 单链表可以看作只有右子树的二叉树——每个节点只有一个 next 指针，相当于二叉树节点只有 right child
  2. 二叉搜索树中序遍历得到有序链表——这常被用来「展平」二叉搜索树
  3. 链表 + 随机指针就是二叉树——每个节点有两个额外指针（left/right），就是二叉树结构
1
2
3
4
5
6
7
8
9
10
11
12
13
// 二叉树展平成链表（LeetCode 114）
function flatten(root) {
  if (!root) return;
  flatten(root.left);
  flatten(root.right);
  // 后序位置
  const right = root.right;
  root.right = root.left;
  root.left = null;
  let node = root;
  while (node.right) node = node.right;
  node.right = right;
}

  这种联系在题目中经常出现，本质上都是把树结构转换成线性结构来方便处理。