理解树结构

⚡ 30 秒速记

• 树 = 连通、无环的层级结构；除根以外每个结点恰好一个父结点
• 度 = 直接子结点个数，度为 0 的是叶子；树的度取所有结点度的最大值
• 深度从根往下数，高度从叶往上数；从 0 还是 1 起算各教材不同，先说清口径
• n 个结点恰好 n - 1 条边：多一条成环，少一条不连通
• 递归先想清楚「函数返回这棵子树的什么信息」；链状退化的树递归深度是 O(n)，可能爆栈

树就是一个没有环、所有结点连在一起的层级结构，除了根，每个结点只有一个父亲。 生活里最像的就是公司组织架构或者电脑里的文件夹，一个上级可以管很多人，但每个人只有一个直属上级。几个术语要分清：度是直接孩子的个数，叶子是没有孩子的结点；深度从根往下数，高度从最远的叶子往上数。不同教材从 0 或 1 起算，比如层数常从 1 开始，我面试时会先说一句「我按根深度为 0 来算」，避免双方对不上。

树的术语容易因为教材口径不同而答乱。下面统一约定根结点深度为 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) 并触发调用栈上限，超深输入应改用显式栈。

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

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