1. 引言
在分析算法复杂度或设计树结构相关的逻辑时，树的深度（depth）与高度（height） 是两个非常关键的属性。虽然这两个概念经常被混淆，但它们的定义和应用场景是完全不同的。本文将从定义、计算方式和复杂度三个方面来阐述它们的区别。
2. 概念解析
✅ 树中每个节点都有两个属性：
- 深度（Depth）：该节点到根节点的边数（edge）。
- 高度（Height）：该节点到其最远叶子节点的边数。
⚠️ 注意：
- 根节点的深度为 0。
- 叶子节点的高度为 0。
- 整棵树的“高度”等于根节点的高度。
- 整棵树的“最大深度”等于最深叶子节点的深度。
3. 图解说明
我们来看两个图示，帮助你更直观理解这两个概念。
✅ 找高度（Find Height）
高度的计算通常采用递归方式，一个节点的高度是其所有子节点中最大高度加一。
✅ 找深度（Find Depth）
深度的计算则从目标节点向上追溯到根节点，统计经过的边数。
4. 示例代码
下面给出 Java 风格的伪代码实现，便于你理解递归与迭代的实现逻辑。
✅ 求节点高度（Height）
algorithm findHeight(Target, Root):
// INPUT
// Target = Target Node
// Root = Tree Root
// OUTPUT
// Target Node Height
height <- 0
for C in Target.children:
tempHeight <- findHeight(C, Root)
if tempHeight > height:
height <- tempHeight
height <- height + 1
return height
踩坑提醒：叶子节点没有子节点，因此其高度为 0。递归时要特别注意边界条件。
✅ 求节点深度（Depth）
algorithm findDepth(Target, Root):
// INPUT
// Target = Target Node
// Root = Tree Root
// OUTPUT
// Target Node Depth
depth <- 0
temp <- Target
while root != temp:
temp <- temp.parent
depth <- depth + 1
return depth
踩坑提醒：要确保每个节点都保存了父节点的引用，否则无法向上追溯。
5. 时间与空间复杂度对比
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 求高度（Height） | O(n) | O(n) | 通常使用 BFS 或递归实现，需遍历整个树 |
| 求深度（Depth） | O(log n) 平均情况 O(n) 最坏情况 |
O(1)（无需额外存储） | 仅需从目标节点回溯到根节点 |
⚠️ 注意：求深度的时间复杂度取决于树的高度，如果是平衡树（如 AVL、红黑树），复杂度为 O(log n)，但在极端不平衡的情况下会退化为 O(n)。
6. 总结
- 深度（Depth） 是从根节点到当前节点的路径长度。
- 高度（Height） 是从当前节点到最远叶子节点的路径长度。
- 整棵树的高度 = 根节点的高度
- 整棵树的最大深度 = 最深叶子节点的深度
- 两者的计算方式不同，复杂度也有差异，理解它们有助于你更准确地分析树结构相关算法的性能。
✅ 建议：在实际开发中，尤其是在处理树形结构（如 DOM 树、文件系统目录结构、数据库索引树）时，务必区分清楚 depth 与 height，否则很容易写出“看起来对但逻辑错”的代码。