数据结构：树篇

发表于 分类于
本文字数： 10k 阅读时长 ≈ 10 分钟

树是一种非常重要的非线性数据结构，在算法和工程中应用极其广泛。本文将从基础概念、遍历算法到常见题型，全面讲解树的相关知识。

一、树的基本概念

1.1 什么是树？

树（Tree）是由 n（n ≥ 0）个节点组成的有限集合。当 n = 0 时，称为空树。

对于任意一棵非空树，满足：

  1. 有且仅有一个特定的节点，称为根节点（Root）
  2. 除根节点外，其余节点可以分为 m（m > 0）个互不相交的有限集合 T1, T2, …, Tm，其中每个集合本身又是一棵树，称为根的子树（Subtree）

1.2 树的相关术语

术语说明
节点（Node）树的基本单位，包含一个数据元素及若干指向子树的指针
根节点（Root）树的顶层节点，没有父节点
父节点（Parent）有子节点的节点，子节点的上一级节点
子节点（Child）父节点的下一级节点
兄弟节点（Sibling）具有相同父节点的节点
叶子节点（Leaf）没有子节点的节点，也叫终端节点
分支节点（Branch）有子节点的节点，也叫非终端节点
路径（Path）从一个节点到另一个节点经过的节点序列
祖先节点（Ancestor）从根到该节点路径上的所有节点
子孙节点（Descendant）该节点的子树中的所有节点

1.3 节点的度、树的度

  • 节点的度（Degree）：一个节点的子节点个数
  • 树的度：树中所有节点的度的最大值
  • N 叉树：每个节点最多有 N 个子节点的树

1.4 深度、高度、层

概念定义示例
深度（Depth）从根节点到该节点的路径长度（根节点深度为 0 或 1）根节点深度 = 0，子节点深度 = 1
高度（Height）从该节点到最远叶子节点的路径长度（叶子节点高度为 0）叶子节点高度 = 0，根节点高度最大
层（Level）根为第 1 层，根的孩子为第 2 层，以此类推根在第 1 层

注意： 深度和高度的定义在不同教材中可能略有不同，有的根节点深度为 1，做题时需注意题目说明。

1.5 节点的数据结构表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// N 叉树节点
class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = []; // 子节点数组
  }
}

// 二叉树节点（最常用）
class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;  // 左子节点
    this.right = null; // 右子节点
  }
}

二、二叉树

二叉树是每个节点最多有两个子节点的树，是最常用的树结构。

2.1 二叉树的性质

  1. 性质 1：二叉树的第 i 层上最多有 2^(i-1) 个节点
  2. 性质 2：深度为 k 的二叉树最多有 2^k - 1 个节点
  3. 性质 3：对于任意一棵二叉树，叶子节点数 = 度为 2 的节点数 + 1

2.2 特殊的二叉树

满二叉树（Full Binary Tree）

除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。

1
2
3
4
5
     1
   /   \
  2     3
 / \   / \
4  5  6  7
  • 深度为 k 的满二叉树有 2^k - 1 个节点
  • 叶子节点都在最后一层

完全二叉树（Complete Binary Tree）

除最后一层外，其他层的节点数都达到最大值，且最后一层的节点都依次排列在最左边。

1
2
3
4
5
     1
   /   \
  2     3
 / \   /
4  5  6
  • 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
  • 完全二叉树可以用数组高效存储（堆就是一种完全二叉树）

完全二叉树的数组存储：

1
2
3
4
5
6
索引:  0  1  2  3  4  5
值:    1  2  3  4  5  6

节点 i 的左子节点: 2*i + 1
节点 i 的右子节点: 2*i + 2
节点 i 的父节点: Math.floor((i-1)/2)

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

对于树中的每个节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。

1
2
3
4
5
     5
   /   \
  3     7
 / \   / \
2  4  6  8
  • 中序遍历 BST 可以得到一个有序数组
  • 查找、插入、删除的平均时间复杂度为 O(logn)
  • 最差情况退化为链表，时间复杂度 O(n)

平衡二叉树（AVL 树）

一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

三、树的遍历

树的遍历是指按照某种规则访问树中的所有节点，且每个节点只访问一次。

3.1 深度优先遍历（DFS）

沿着树的深度遍历树的节点，尽可能深地搜索树的分支。

前序遍历（Pre-order）

访问顺序： 根 → 左 → 右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 递归写法
function preorder(root) {
  if (!root) return;
  console.log(root.value);  // 先访问根
  preorder(root.left);      // 再遍历左子树
  preorder(root.right);     // 最后遍历右子树
}

// 迭代写法
function preorderIterative(root) {
  if (!root) return [];
  const result = [];
  const stack = [root];

  while (stack.length) {
    const node = stack.pop();
    result.push(node.value);
    // 注意：先压入右，再压入左（栈是后进先出）
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}

中序遍历（In-order）

访问顺序： 左 → 根 → 右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 递归写法
function inorder(root) {
  if (!root) return;
  inorder(root.left);       // 先遍历左子树
  console.log(root.value);   // 再访问根
  inorder(root.right);      // 最后遍历右子树
}

// 迭代写法
function inorderIterative(root) {
  if (!root) return [];
  const result = [];
  const stack = [];
  let current = root;

  while (current || stack.length) {
    // 一直向左走，把所有左节点入栈
    while (current) {
      stack.push(current);
      current = current.left;
    }
    // 出栈，访问
    current = stack.pop();
    result.push(current.value);
    // 转向右子树
    current = current.right;
  }
  return result;
}

注意： 二叉搜索树的中序遍历是有序的！

后序遍历（Post-order）

访问顺序： 左 → 右 → 根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 递归写法
function postorder(root) {
  if (!root) return;
  postorder(root.left);      // 先遍历左子树
  postorder(root.right);     // 再遍历右子树
  console.log(root.value);   // 最后访问根
}

// 迭代写法（方法一：反转前序）
function postorderIterative(root) {
  if (!root) return [];
  const result = [];
  const stack = [root];

  while (stack.length) {
    const node = stack.pop();
    result.push(node.value);
    // 先压入左，再压入右
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  // 后序 = 根右左 → 反转 → 左右根
  return result.reverse();
}

// 迭代写法（方法二：标记法）
function postorderIterative2(root) {
  if (!root) return [];
  const result = [];
  const stack = [[root, false]];

  while (stack.length) {
    const [node, visited] = stack.pop();
    if (visited) {
      result.push(node.value);
    } else {
      stack.push([node, true]);
      if (node.right) stack.push([node.right, false]);
      if (node.left) stack.push([node.left, false]);
    }
  }
  return result;
}

3.2 广度优先遍历（BFS）

也叫层序遍历，按照树的层次从上到下、从左到右访问节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 基础层序遍历
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length) {
    const node = queue.shift();
    result.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

// 按层输出（带层级信息）
function levelOrderWithLevel(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(currentLevel);
  }
  return result;
}

3.3 遍历应用场景

遍历方式应用场景
前序遍历复制树、前缀表达式
中序遍历二叉搜索树排序、中缀表达式
后序遍历删除树、后缀表达式、计算目录大小
层序遍历求树的宽度、打印树、找最短路径

四、常见题型

树的题目主要分为三类：搜索类、构建类、修改类，其中搜索类最多。

4.1 搜索类

题型一：路径和问题

LeetCode 112：路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

1
2
3
4
5
6
7
8
9
10
11
12
var hasPathSum = function(root, targetSum) {
  if (!root) return false;

  // 到达叶子节点
  if (!root.left && !root.right) {
    return root.val === targetSum;
  }

  // 减去当前节点值，继续递归
  return hasPathSum(root.left, targetSum - root.val) ||
         hasPathSum(root.right, targetSum - root.val);
};

LeetCode 113：路径总和 II

给定一个二叉树和一个目标和，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var pathSum = function(root, targetSum) {
  const result = [];

  function backtrack(node, path, sum) {
    if (!node) return;

    path.push(node.val);
    sum -= node.val;

    // 到达叶子节点且和为 0
    if (!node.left && !node.right && sum === 0) {
      result.push([...path]);
    } else {
      backtrack(node.left, path, sum);
      backtrack(node.right, path, sum);
    }

    // 回溯
    path.pop();
  }

  backtrack(root, [], targetSum);
  return result;
};

题型二：树的最大深度

LeetCode 104：二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// DFS 递归
var maxDepth = function(root) {
  if (!root) return 0;
  const left = maxDepth(root.left);
  const right = maxDepth(root.right);
  return Math.max(left, right) + 1;
};

// BFS 层序遍历
var maxDepthBFS = function(root) {
  if (!root) return 0;
  let depth = 0;
  const queue = [root];

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

题型三：对称二叉树

LeetCode 101：对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var isSymmetric = function(root) {
  if (!root) return true;

  function isMirror(left, right) {
    // 都为空，对称
    if (!left && !right) return true;
    // 一个为空，一个不为空，不对称
    if (!left || !right) return false;
    // 值不相等，不对称
    if (left.val !== right.val) return false;
    // 递归：左的左 vs 右的右，左的右 vs 右的左
    return isMirror(left.left, right.right) && isMirror(left.right, right.left);
  }

  return isMirror(root.left, root.right);
};

题型四：二叉搜索树的验证

LeetCode 98：验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 方法一：递归
var isValidBST = function(root) {
  function helper(node, min, max) {
    if (!node) return true;
    // 当前节点必须在 (min, max) 范围内
    if (node.val <= min || node.val >= max) return false;
    // 左子树最大不能超过当前节点，右子树最小不能小于当前节点
    return helper(node.left, min, node.val) && helper(node.right, node.val, max);
  }
  return helper(root, -Infinity, Infinity);
};

// 方法二：中序遍历（BST 中序一定是升序）
var isValidBSTInorder = function(root) {
  let prev = -Infinity;
  let isValid = true;

  function inorder(node) {
    if (!node || !isValid) return;
    inorder(node.left);
    if (node.val <= prev) {
      isValid = false;
      return;
    }
    prev = node.val;
    inorder(node.right);
  }

  inorder(root);
  return isValid;
};

4.2 构建类

题型一：从前序与中序遍历序列构造二叉树

LeetCode 105：从前序与中序遍历序列构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var buildTree = function(preorder, inorder) {
  if (!preorder.length || !inorder.length) return null;

  // 前序第一个是根节点
  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);

  // 在中序中找到根节点的位置
  const rootIndex = inorder.indexOf(rootVal);

  // 左子树：前序 [1..rootIndex]，中序 [0..rootIndex-1]
  root.left = buildTree(
    preorder.slice(1, rootIndex + 1),
    inorder.slice(0, rootIndex)
  );

  // 右子树：前序 [rootIndex+1..]，中序 [rootIndex+1..]
  root.right = buildTree(
    preorder.slice(rootIndex + 1),
    inorder.slice(rootIndex + 1)
  );

  return root;
};

题型二：从中序与后序遍历序列构造二叉树

LeetCode 106：从中序与后序遍历序列构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var buildTree = function(inorder, postorder) {
  if (!inorder.length || !postorder.length) return null;

  // 后序最后一个是根节点
  const rootVal = postorder[postorder.length - 1];
  const root = new TreeNode(rootVal);

  // 在中序中找到根节点的位置
  const rootIndex = inorder.indexOf(rootVal);

  // 左子树：中序 [0..rootIndex-1]，后序 [0..rootIndex-1]
  root.left = buildTree(
    inorder.slice(0, rootIndex),
    postorder.slice(0, rootIndex)
  );

  // 右子树：中序 [rootIndex+1..]，后序 [rootIndex..length-2]
  root.right = buildTree(
    inorder.slice(rootIndex + 1),
    postorder.slice(rootIndex, postorder.length - 1)
  );

  return root;
};

4.3 修改类

题型一：翻转二叉树

LeetCode 226：翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var invertTree = function(root) {
  if (!root) return null;

  // 交换左右子节点
  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  // 递归翻转
  invertTree(root.left);
  invertTree(root.right);

  return root;
};

题型二：二叉树展开为链表

LeetCode 114：二叉树展开为链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 方法一：后序遍历
var flatten = function(root) {
  if (!root) return;

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

  // 保存右子树
  const right = root.right;

  // 将左子树移到右边
  root.right = root.left;
  root.left = null;

  // 找到最右边的节点，接上原来的右子树
  let p = root;
  while (p.right) {
    p = p.right;
  }
  p.right = right;
};

4.4 进阶题型

题型一：最近公共祖先（LCA）

LeetCode 236：二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
var lowestCommonAncestor = function(root, p, q) {
  if (!root || root === p || root === q) return root;

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

  // 如果左右都找到，说明当前是 LCA
  if (left && right) return root;

  // 否则返回找到的那个
  return left || right;
};

LeetCode 235：二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
// BST 的 LCA 更简单
var lowestCommonAncestor = function(root, p, q) {
  // 如果 p 和 q 都在左边，去左边找
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestor(root.left, p, q);
  }
  // 如果 p 和 q 都在右边，去右边找
  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestor(root.right, p, q);
  }
  // 否则当前就是 LCA
  return root;
};

题型二：二叉树的直径

LeetCode 543：二叉树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var diameterOfBinaryTree = function(root) {
  let maxDiameter = 0;

  function depth(node) {
    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;
};

五、树的常见套路

5.1 递归三部曲

树的题目大多可以用递归解决，记住递归三部曲：

  1. 确定递归函数的参数和返回值

    • 需要哪些参数？
    • 需要返回什么？

  2. 确定终止条件

    • 节点为空？
    • 到达叶子节点？
    • 满足某种条件？

  3. 确定单层递归逻辑

    • 先处理左子树？
    • 先处理右子树？
    • 当前节点做什么？

5.2 遍历选择

情况推荐遍历
需要先处理父节点前序遍历
需要先处理子节点后序遍历
二叉搜索树相关中序遍历
按层处理、最短路径层序遍历

5.3 时间复杂度分析

操作时间复杂度
遍历树O(n)
BST 查找/插入/删除（平均）O(logn)
BST 查找/插入/删除（最坏）O(n)
平衡树所有操作O(logn)

5.4 空间复杂度分析

情况空间复杂度
递归遍历O(h)，h 是树的高度，最坏 O(n)
层序遍历O(n)，最坏情况是完全二叉树的最后一层

六、总结

6.1 核心知识点

  1. 基础概念：根、叶子、父节点、子节点、深度、高度、度
  2. 特殊二叉树：满二叉树、完全二叉树、二叉搜索树、平衡树
  3. 遍历算法：
    • DFS：前序、中序、后序（递归 + 迭代）
    • BFS：层序遍历
  4. 常见题型：搜索类、构建类、修改类

6.2 做题建议

  1. 先掌握递归：树的题目 90% 可以用递归解决
  2. 多画图解：画图能帮助你理清思路
  3. 记住模板：遍历模板、回溯模板要熟练
  4. 分类刷题：按题型分类练习，总结规律

树的题目变化很多，但核心就是遍历！只要掌握了遍历，大多数题目都能迎刃而解！