java - N 叉树的高度

Question

我尝试编写一个名为 getHeight() 的方法来计算 N 叉树的高度。我的尝试不起作用。这是我正在使用的树界面:

public interface MyTree  {
    Tree getSubTree(int i) ;//returns a subtree
    boolean isLeaf() ;//returns true if the node is a leaf
    int getDegree() ; 
}   

这是我写的一段代码:

public int getHeight(){

    for(int i = 0 ; i<getDegree()-1 ; ++i){  

        if(isLeaf()){
            return 0; 

        }else{
            return 1 + Math.Max(getSubtree(i).getHeight() , getSubtree(i+1).getHeight() ; 
        }
    }
}

如何修复此方法？

Answer 1

您的问题在这里:

 return 1 + getSubtree(i).getHeight(); 

一旦计算出 1 + 单个子树的高度，您就会从该方法返回。您实际需要做的是在每个子树上调用 getHeight() ，并返回 1 + 每个子树的最大值。 (如果您的树具有任何平衡属性，这可以简化。)

例如，如果您调用此方法的树有三个子树，高度分别为 2、4 和 5，则您的代码将在第一个子树上调用 getHeight() 并看到 2，然后立即返回 3，而不是检查剩余子树上的 getHeight() 来查找是否存在更高的子树(高度为 5 的子树)。