如何用JavaScript实现非二叉树节点的层级计算方法？

给定非二叉树结构：

root
                         /      \
                        A        B
                       / \      / \
                      C   D    E   F
                    / \ \
                   G  H  I

需要为树中的节点实现getLevel方法，调用时返回节点所在层级（根节点层级为0，例如C.getLevel()应返回2）。每个节点仅包含name（节点名称）和children（直接子节点数组）两个属性。

尝试用递归解决但思路有误，初始代码如下：

getLevel(level = 0) {
    if (this.children.length === 0) {
        return level;
    }

    for (let child of this.children) {
        level = child.getLevel(level + 1);
    }
}

你的代码逻辑完全搞反了：当前代码是递归遍历子节点，最后返回的是当前节点最深子节点的层级，根本不是当前节点自己的层级（比如调用C.getLevel()会返回3，而不是预期的2）。

要实现正确的getLevel方法，核心是找到当前节点在整个树中的位置，有两种可行方案：

方案1：给节点添加父节点引用（推荐） #

如果可以在构建树时给每个节点添加parent属性，就能通过递归向上追溯父节点计算层级：

节点的getLevel实现 #

getLevel() {
    // 根节点没有父节点，直接返回0
    if (!this.parent) {
        return 0;
    }
    // 当前节点层级 = 父节点层级 + 1
    return this.parent.getLevel() + 1;
}

构建树时设置parent属性示例 #

// 构建根节点
const root = { name: 'root', children: [], parent: null };
// 构建子节点并绑定父节点
const A = { name: 'A', children: [], parent: root };
root.children.push(A);
const C = { name: 'C', children: [], parent: A };
A.children.push(C);
// 其他节点以此类推...

这种方式效率更高，每次调用getLevel最多递归到根节点，时间复杂度更低。

方案2：不修改节点结构，从根节点遍历查找 #

如果不能修改节点原有结构，可以实现工具函数从根节点递归遍历，找到目标节点时返回对应层级：

工具函数+节点方法实现 #

// 工具函数：从根节点查找目标节点的层级
function findNodeLevel(root, targetNode, currentLevel = 0) {
    // 找到目标节点，返回当前层级
    if (root === targetNode) {
        return currentLevel;
    }
    // 遍历所有子节点递归查找
    for (const child of root.children) {
        const level = findNodeLevel(child, targetNode, currentLevel + 1);
        if (level !== -1) {
            return level;
        }
    }
    // 当前分支未找到目标节点，返回-1
    return -1;
}

// 节点的getLevel方法（需要传入根节点）
getLevel(root) {
    return findNodeLevel(root, this);
}

调用示例 #

// 假设root是树的根节点
console.log(C.getLevel(root)); // 输出2

这种方式每次调用都需要从根节点遍历整个树，时间复杂度为O(n)，适合无法修改节点结构的场景。

内容的提问来源于stack exchange，提问作者Luk