algorithm - 如何计算一棵树的高度

Question

我正在尝试学习 DSA，但遇到了一个问题。

如何计算树的高度。我的意思是普通树，而不是像 BT 或 BST 这样的树的任何特定实现。

我试过谷歌，但似乎每个人都在谈论二叉树，而普通树没有任何可用的东西。

谁能帮我重定向到某些页面或文章来计算树的高度。

Answer 1

假设树中的一个典型节点表示为 Java 类。

class Node{
    Entry entry;
    ArrayList<Node> children;
    Node(Entry entry, ArrayList<Node> children){
        this.entry = entry;
        this.children = children;
    }   
    ArrayList<Node> getChildren(){
        return children;
    }   
}  

然后一个简单的高度函数可以是 -

int getHeight(Node node){
    if(node == null){
        return 0;
    }else if(node.getChildren() == null){
        return 1;
    } else{
       int childrenMaxHeight = 0;
       for(Node n : node.getChildren()){
           childrenMaxHeight = Math.max(childrenMaxHeight, getHeight(n));
       }
       return 1 + childrenMaxHeight;
    }
}

然后你只需要调用这个函数传递树的根作为参数。由于它恰好遍历所有节点一次，因此运行时间为 O(n)。