理解树结构

⚡ 30 秒速记

• 树是无环的连通层级结构；除根结点外，每个结点恰好有一个父结点，可以有零个或多个子结点
• 结点的度是直接子结点数量，叶子结点的度为 0；树的度是所有结点度的最大值
• 深度从根向下数，高度从叶向上数；面试前必须先约定根深度和叶高度从 0 还是 1 开始
• 含 n 个结点的树恰有 n - 1 条边；多一条边会成环，少一条边会不连通
• 递归处理树时先定义“函数返回的子树信息”，再组合左右或所有孩子，避免只背遍历模板

树本质上是无环且连通的层级结构，除根结点外，每个结点只有一个父结点，但可以有多个子结点。 结点的度表示直接子结点数量，度为 0 的是叶子结点，而树的度取所有结点度的最大值。深度从根向下计算，高度从叶子向上计算，不同教材可能从 0 或 1 起算，所以面试时要先讲清口径。含 n 个结点的树有 n - 1 条边；递归处理时应先定义函数返回什么子树信息，并注意退化成链后递归栈可能达到 O(n)。

树的术语容易因为教材口径不同而答乱。下面统一约定根结点深度为 0、叶结点高度为 0：结点深度等于从根到它的边数，结点高度等于从它到最远叶子的边数。若题目把层数从 1 开始，只需整体加一，算法本身不变。面试时先说清口径，比死背某个数字更可靠。

function measureTree(root) {
  let maxDepth = -1
  let nodeCount = 0

  function height(node, depth) {
    if (node === null) return -1
    nodeCount += 1
    maxDepth = Math.max(maxDepth, depth)
    const childHeights = (node.children ?? []).map((child) => height(child, depth + 1))
    return 1 + Math.max(-1, ...childHeights)
  }

  const treeHeight = height(root, 0)
  return { nodeCount, maxDepth, treeHeight }
}

空树返回高度 -1，因此叶结点会得到 1 + (-1) = 0。每个结点只访问一次，时间复杂度 O(n)；递归栈等于树高 O(h)，退化成链时可能达到 O(n) 并触发调用栈上限，超深输入应改用显式栈。

在理解计算机世界的树结构之前，大家不妨回忆一下现实世界中的树有什么特点：一棵树往往只有一个树根，向上生长后，却可以伸展出无数的树枝、树枝上会长出树叶。由树根从泥土中吸收水、无机盐等营养物质，源源不断地输送到树枝与树叶的那一端。一棵树往往呈现这样的基本形态：

数据结构中的树，首先是对现实世界中树的一层简化：把树根抽象为“根结点”，树枝抽象为“边”，树枝的两个端点抽象为“结点”，树叶抽象为“叶子结点”。抽象后的树结构如下：