无左右引用的树的根节点高度计算异常排查求助

我来帮你搞定这个树高度计算的问题！首先咱们先梳理下你的代码问题所在，再给出符合预期的解法。

你的代码核心问题 #

你当前的思路和实现存在两个关键偏差：

• 递归逻辑完全没用到返回值：你遍历了所有子节点，但只是单纯调用递归，没有利用子节点的高度结果来计算当前节点的高度。反而每个节点都单独往上遍历到根，计算自己到根的路径长度，这就导致输出一堆叶子节点到根的距离，而不是整棵树的最大高度。
• 对树高度的定义理解有误：树的高度是根到最远叶子节点的最长路径上的节点数（或边数），你现在输出的是所有叶子到根的距离集合，而我们需要的是这个集合里的最大值。

正确的递归解法（推荐） #

树高度的经典递归思路是：每个节点的高度 = 1 + 所有子节点高度的最大值。叶子节点没有子节点，所以它的高度是1（按节点数计算，符合你的预期结果）。

public int height(){ 
    System.out.print("Height: "); 
    int rootHeight = height(root);
    System.out.println(rootHeight);
    return rootHeight; 
} 

private int height(TNode tn){ 
    // 空节点作为递归终止条件，高度为0
    if (tn == null) return 0;
    
    int maxChildHeight = 0;
    // 遍历所有子节点，找到最高的子树高度
    for (TNode cn: tn.getChildren()){ 
        int childHeight = height(cn);
        if (childHeight > maxChildHeight) {
            maxChildHeight = childHeight;
        }
    } 
    // 当前节点的高度 = 最高子树高度 + 1（加上当前节点本身）
    return maxChildHeight + 1; 
}

代码解释

1. 递归终止条件：当节点为null时返回0，处理叶子节点的子节点（空）的情况。
2. 遍历子节点：递归计算每个子节点的高度，记录其中的最大值。
3. 计算当前节点高度：当前节点的高度是子树的最大高度加1，因为当前节点在子树的上层。
4. 输出结果：根节点的高度就是整棵树的高度，直接输出这个值即可，不会再出现多余的数字。

如果你想坚持遍历节点找最大值（不推荐） #

如果一定要用“遍历所有节点，计算每个节点到根的距离，取最大值”的思路，也可以实现，但效率更低（时间复杂度O(n*h)，n是节点数，h是树高）：

public int height(){ 
    System.out.print("Height: "); 
    int maxDepth = 0;
    // 用队列做广度优先遍历所有节点
    Queue<TNode> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        TNode current = queue.poll();
        int depth = 0;
        TNode temp = current;
        // 计算当前节点到根的距离
        while (temp != null) {
            depth++;
            temp = temp.getParent();
        }
        // 更新最大深度
        if (depth > maxDepth) {
            maxDepth = depth;
        }
        // 将当前节点的所有子节点加入队列
        queue.addAll(current.getChildren());
    }
    
    System.out.println(maxDepth);
    return maxDepth; 
}

总结 #

核心问题是你对树高度的计算逻辑理解有误，应该从下往上递归计算子树高度，而不是从上往下数每个节点到根的距离。递归方法简洁高效，符合树结构的常规遍历思路，能直接得到你需要的根节点高度。

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