理解树节点深度
在树形数据结构中，节点的深度（depth）或层级（level）是指从根节点到该节点所经过的边的数量。通常，根节点的深度定义为0。例如，在一个树中：
root (深度 0)
/ \
A (深度 1) B (深度 1)
/ \ / \
C D E F (深度 2)
/ \ \
G H I (深度 3)节点 C 的深度是2，节点 G 的深度是3。本教程将提供两种基于递归的JavaScript实现方法来计算任意给定节点的深度。
节点结构定义
为了实现树节点的深度计算，我们首先需要定义一个基本的 Node 类。每个节点至少需要包含一个标识符（如 name）和其直接子节点的数组（children）。
class Node {
constructor(name, ...children) {
this.name = name;
this.children = children;
}
// 后续深度计算方法将添加到此类中
}这个 Node 类允许我们构建任意分支的非二叉树。children 参数使用剩余参数语法，方便在构造时直接传入子节点。
方法一：从根节点开始按名称查找并计算深度
这种方法从树的根节点开始遍历，尝试找到目标节点。一旦找到，就返回其相对于当前节点的深度。如果目标节点是当前节点本身，则深度为0；否则，它将是某个子节点的深度加1。
立即学习“Java免费学习笔记（深入）”；
实现思路：
- 基本情况： 如果当前节点的名称与目标名称匹配，则说明找到了目标节点，其深度为0。
- 递归步骤： 遍历当前节点的所有子节点。对每个子节点递归调用深度计算方法。
- 结果处理： 如果子节点的递归调用返回的深度值大于等于0（表示在子树中找到了目标节点），则当前节点的深度就是子节点返回的深度加1。
- 未找到情况： 如果遍历完所有子节点都没有找到目标节点，则返回 -1。
示例代码：
class Node {
constructor(name, ...children) {
this.name = name;
this.children = children;
}
/**
* 从当前节点开始，查找指定名称的节点并计算其深度。
* @param {string} targetName 目标节点的名称。
* @returns {number} 目标节点的深度（相对于调用此方法的节点），如果未找到则返回 -1。
*/
getDepth(targetName) {
// 基本情况：如果当前节点就是目标节点，深度为0
if (this.name === targetName) {
return 0;
}
// 递归步骤：遍历子节点
for (const child of this.children) {
const depth = child.getDepth(targetName); // 在子节点中查找
// 如果在子树中找到了目标节点
if (depth >= 0) {
return depth + 1; // 目标节点的深度是子节点深度加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 depthC = root.getDepth("C");
console.log(`节点 "C" 的深度: ${depthC}`); // 输出: 节点 "C" 的深度: 2
// 计算节点 "I" 的深度
const depthI = root.getDepth("I");
console.log(`节点 "I" 的深度: ${depthI}`); // 输出: 节点 "I" 的深度: 3
// 计算不存在的节点 "X" 的深度
const depthX = root.getDepth("X");
console.log(`节点 "X" 的深度: ${depthX}`); // 输出: 节点 "X" 的深度: -1注意事项：
- 此方法要求从树的根节点调用，并传入目标节点的名称。
- 如果树中存在同名节点，此方法将返回第一个匹配到的节点的深度（通常是先序遍历中遇到的第一个）。
- 返回 -1 作为未找到的标识符，这是一种常见的做法。
方法二：从目标节点开始向上回溯计算深度
这种方法与前一种思路相反，它在目标节点上调用方法，并传入整个树的根节点。它通过检查当前节点是否是传入根节点的子节点来“向上”回溯，直到找到根节点。
实现思路：
- 基本情况： 如果当前节点就是传入的根节点，则其深度为0。
- 递归步骤： 遍历传入根节点的所有子节点。对每个子节点，递归调用深度计算方法，将当前节点（this）作为目标节点，将子节点作为新的“根”进行检查。
- 结果处理： 如果子节点的递归调用返回的深度值大于等于0（表示目标节点在子树中），则目标节点的深度就是子节点返回的深度加1。
- 未找到情况： 如果遍历完所有子节点都没有找到目标节点，则返回 -1。
示例代码：
class Node {
constructor(name, ...children) {
this.name = name;
this.children = children;
}
/**
* 从当前节点开始，向上回溯到指定根节点，计算当前节点的深度。
* @param {Node} root 树的根节点。
* @returns {number} 当前节点相对于传入根节点的深度，如果当前节点不在该根节点下则返回 -1。
*/
getDepthWithRespectTo(root) {
// 基本情况：如果当前节点就是根节点，深度为0
if (this === root) {
return 0;
}
// 递归步骤：遍历根节点的子节点，检查当前节点是否在其中
// 注意：这里的“向上回溯”是通过检查目标节点是否是根节点的子节点来实现的
for (const child of root.children) {
// 在子节点中查找目标节点 (this)
const depth = this.getDepthWithRespectTo(child);
// 如果在子树中找到了目标节点
if (depth >= 0) {
return depth + 1; // 目标节点的深度是子节点深度加1
}
}
// 未在当前根节点及其子树中找到目标节点
return -1;
}
}
// 构建示例树，并保持对节点 "C" 的引用
let nodeC;
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" 的深度，从节点 "C" 调用方法并传入根节点
const depthC = nodeC.getDepthWithRespectTo(root);
console.log(`节点 "C" 的深度: ${depthC}`); // 输出: 节点 "C" 的深度: 2
// 假设我们有节点 G 的引用
const nodeG = nodeC.children[0];
const depthG = nodeG.getDepthWithRespectTo(root);
console.log(`节点 "G" 的深度: ${depthG}`); // 输出: 节点 "G" 的深度: 3注意事项：
- 此方法要求你已经拥有目标节点的引用，并传入整个树的根节点。
- 它通过比较节点实例（this === root）来判断是否找到。
- 同样使用 -1 表示未找到。
总结
本教程介绍了两种在JavaScript中计算非二叉树节点深度的递归方法：
- 从根节点向下查找（getDepth(targetName)）：适用于已知目标节点名称，从根节点开始遍历查找。
- 从目标节点向上回溯（getDepthWithRespectTo(root)）：适用于已知目标节点实例，从目标节点出发，传入根节点进行验证。
两种方法的核心都是利用递归的特性，通过定义明确的基本情况和递归步骤来解决问题。在实际应用中，选择哪种方法取决于你已知的信息（是节点名称还是节点实例）以及你的代码结构偏好。理解递归的退出条件和如何累加深度是实现这些功能的关键。
