树节点深度概念
在树形数据结构中，节点的“深度”（depth）或“层级”（level）是一个核心概念。通常，根节点的深度定义为0，其直接子节点的深度为1，依此类推。对于非二叉树，每个节点可以拥有任意数量的子节点，这使得计算特定节点的深度成为一项常见的任务。
我们的目标是设计一个方法，给定一个树中的节点，能够准确返回其相对于根节点的深度。树中的每个节点至少包含两个属性：一个用于标识节点的 name 和一个存储其直接子节点的数组 children。由于树的天然递归特性，递归算法是解决此类问题的理想选择。
核心实现思路：递归遍历
要确定一个特定节点的深度，最关键的思路是从树的根节点开始进行遍历。当我们从根节点向下遍历时，每深入一层，深度值就增加1。当找到目标节点时，当前累积的深度值即为该节点的深度。如果遍历完所有子树仍未找到目标节点，则表示该节点不在当前搜索路径中。
我们将探讨两种主要的递归实现方案。
方案一：从根节点向下搜索目标节点
这种方法最为直观，它将深度计算逻辑封装在树的节点类中，并从根节点发起调用，传入目标节点的名称进行搜索。
立即学习“Java免费学习笔记（深入）”；
方法描述
getDepth(targetName) 方法被定义在 Node 类上，并由树的根节点调用。它接收一个 targetName 参数，表示我们想要查找其深度的目标节点的名称。
递归逻辑
-
基线条件 (Base Case):
- 如果当前节点的 name 与 targetName 匹配，说明我们找到了目标节点。此时，该节点的深度就是0（相对于当前搜索起点）。
- 如果当前节点没有子节点，并且它也不是目标节点，那么目标节点不在当前路径中，返回一个表示“未找到”的值（例如 -1）。
-
递归步骤 (Recursive Step):
- 遍历当前节点的所有子节点。
- 对每个子节点递归调用 child.getDepth(targetName)。
- 如果子节点返回的深度值大于或等于0（表示在子树中找到了目标节点），那么目标节点的实际深度就是子节点返回的深度值加1（因为当前节点比其子节点高一层）。
- 如果遍历完所有子节点都没有找到目标节点，则返回 -1。
示例代码
class Node {
constructor(name, ...children) {
this.name = name;
this.children = children; // children是一个数组，可以包含任意数量的子节点
}
/**
* 从当前节点开始，向下搜索指定名称的节点，并返回其深度。
* 如果当前节点就是目标节点，深度为0。
* 如果未找到，返回-1。
* @param {string} targetName - 目标节点的名称
* @returns {number} - 目标节点的深度，如果未找到则为-1
*/
getDepth(targetName) {
// 基线条件1：如果当前节点就是目标节点，其深度为0
if (this.name === targetName) {
return 0;
}
// 递归步骤：遍历所有子节点
for (const child of this.children) {
// 递归调用子节点的getDepth方法
const depthInChildSubtree = child.getDepth(targetName);
// 如果在子树中找到了目标节点（返回值 >= 0）
if (depthInChildSubtree >= 0) {
// 目标节点的深度是子树深度加1
return depthInChildSubtree + 1;
}
}
// 基线条件2：遍历完所有子节点仍未找到，返回-1
return -1;
}
}
// 构建示例树结构
const root = new Node("root",
new Node("A",
new Node("C",
new Node("G"),
new Node("H"),
new Node("I")
),
new Node("D")
),
new Node("B",
new Node("E"),
new Node("F")
)
);
// 示例调用：计算节点"C"的深度
const depthOfC = root.getDepth("C");
console.log(`节点 "C" 的深度: ${depthOfC}`); // 预期输出: 2
// 示例调用：计算节点"G"的深度
const depthOfG = root.getDepth("G");
console.log(`节点 "G" 的深度: ${depthOfG}`); // 预期输出: 3
// 示例调用：计算不存在的节点"X"的深度
const depthOfX = root.getDepth("X");
console.log(`节点 "X" 的深度: ${depthOfX}`); // 预期输出: -1注意事项
- 此方法要求从树的根节点开始调用，并传入目标节点的名称。
- 返回值为 -1 表示在整个树中未找到指定名称的节点。
- 这种方法是最常用且最直观的，因为它模拟了我们从根部向下探索树的过程。
方案二：从目标节点向上追溯至根节点（通过根节点参数）
第二种方法是另一种思维方式，它将深度计算方法定义在 Node 类上，但由目标节点自身调用，并传入树的根节点作为参数。
方法描述
getDepthWithRespectTo(root) 方法由我们想要获取深度的 目标节点 调用，并传入整个树的 root 节点。其核心思想是，如果当前节点就是根节点，则深度为0；否则，在根节点的子节点中递归查找当前节点。
递归逻辑
-
基线条件 (Base Case):
- 如果当前节点 (this) 就是传入的 root 节点，那么它的深度就是0。
-
递归步骤 (Recursive Step):
- 遍历 root 节点的所有子节点。
- 对每个子节点 parent，递归调用 this.getDepthWithRespectTo(parent)。这里 this 始终是目标节点。
- 如果递归调用返回的深度值大于或等于0（表示目标节点在某个子树中被找到），那么目标节点的实际深度就是子树深度加1。
- 如果遍历完 root 的所有子节点都没有找到目标节点，则返回 -1。
示例代码
class Node {
constructor(name, ...children) {
this.name = name;
this.children = children;
}
/**
* 计算当前节点相对于给定根节点的深度。
* 如果当前节点就是根节点，深度为0。
* 如果当前节点不在以给定根节点为起点的树中，返回-1。
* @param {Node} root - 树的根节点
* @returns {number} - 当前节点的深度，如果未找到则为-1
*/
getDepthWithRespectTo(root) {
// 基线条件1：如果当前节点就是传入的根节点，深度为0
if (this === root) {
return 0;
}
// 递归步骤：在根节点的子节点中查找当前节点
for (const child of root.children) {
// 递归调用，尝试在child为根的子树中找到当前节点
const depth = this.getDepthWithRespectTo(child);
// 如果在子树中找到了当前节点（返回值 >= 0）
if (depth >= 0) {
// 当前节点的深度是子树深度加1
return depth + 1;
}
}
// 基线条件2：遍历完所有子节点仍未找到，返回-1
return -1;
}
}
// 构建示例树结构，并保留对节点"C"的引用
let nodeC; // 用于保存对节点C的引用
const root = new Node("root",
new Node("A",
nodeC = new Node("C", // 节点C被赋值给nodeC
new Node("G"),
new Node("H"),
new Node("I")
),
new Node("D")
),
new Node("B",
new Node("E"),
new Node("F")
)
);
// 示例调用：计算节点"C"相对于根节点的深度
const depthOfC_alt = nodeC.getDepthWithRespectTo(root);
console.log(`节点 "C" 的深度 (方案二): ${depthOfC_alt}`); // 预期输出: 2
// 假设我们有一个不在树中的节点
const nodeX = new Node("X");
const depthOfX_alt = nodeX.getDepthWithRespectTo(root);
console.log(`节点 "X" 的深度 (方案二): ${depthOfX_alt}`); // 预期输出: -1注意事项
- 此方法需要你已经拥有目标节点的引用，并将其作为 this 调用方法，同时传入树的根节点。
- 从逻辑上讲，它是在根节点的子树中查找当前调用方法的节点。
- 虽然功能上等价于方案一，但在实际应用中，方案一（从根向下搜索指定名称）可能更常见和直观，因为它更符合我们查找一个已知名称节点的思维模式。
总结与最佳实践
本文介绍了两种在JavaScript中计算非二叉树节点深度的递归方法。
-
方案一：root.getDepth(targetName)
- 从树的根节点开始向下遍历，查找指定名称的节点。
- 逻辑清晰，易于理解和实现。
- 适用于已知目标节点名称，需要从根节点开始搜索的场景。
-
方案二：targetNode.getDepthWithRespectTo(root)
- 由目标节点调用，传入根节点，在根的子树中递归查找自身。
- 适用于已经持有目标节点引用，并需要计算其相对于特定根节点深度的场景。
选择哪种方案取决于具体的应用场景和偏好。 在大多数情况下，方案一由于其直观的搜索逻辑和通过名称查找的便利性，会是更常用的选择。两种方案都利用了递归的强大功能，以简洁高效的方式解决了树形结构的深度计算问题。
在实现时，务必注意递归的基线条件和返回值，特别是当目标节点未找到时的处理，通常返回一个负值（如-1）来表示。这有助于避免无限递归并正确处理异常情况。理解并熟练运用递归是处理树形数据结构的关键技能之一。
