我正在尝试学习DSA，并陷入一个问题。
如何计算树的高度。我的意思是普通树，而不是像BT或BST这样的树的任何特定实现。
我试过谷歌，但似乎每个人都在谈论二叉树，而普通树没有任何可用。
任何人都可以帮助我重定向到某些页面或文章来计算树的高度。
可以说树中的典型节点表示为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）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句