0

我很难完成这个算法来找到具有多个孩子（不是二进制）的树的高度。

有谁知道这是哪里出错了？

private int getHeight(Node<T> root, int height, int result){

        if (root.getChildren().size()==0) {
            return height;
        }
        height++;

        //Iterate every child
        for (Node<T> childNode  : root.getChildren()) {

            //Get the height again
            height =getHeight(childNode, height, result);

            //Update if new high result
            if (height>result) {
                result = height;
            }

            height = 0;
        }

        //Return highest point
        return result;
    }
4

2 回答 2

1

您通过添加高度和结果参数使其变得更加困难。

在函数中，找到每个孩子的身高。保持最大。返回 1 + 最大高度。

像这样的东西（未经测试，未编译）：

private int getHeight(Node<T> root){

    int max = 0;
    for (Node<T> childNode  : root.getChildren()) {
        int height = getHeight(childNode);
        if (height > max)
            max = height;
    }
    return max + 1;
}
于 2013-09-14T02:10:26.643 回答
1

您计算身高的方式非常尴尬，并且有很多地方可能出现错误，例如您将身高加一然后得到孩子的身高。

我建议做一个更简单的递归函数，它类似于你正在做的那个。

首先，你可以去掉第二个和第三个参数，然后你可以改变代码看起来更像这样：

private int getHeight(Node<T> root){

    if (root.getChildren().size()==0) {
        return 1;
    }

    int height;
    //Iterate every child
    for (Node<T> childNode  : root.getChildren()) {

        //Get the height again
        int childHeight = getHeight(childNode);

        //Update if new high result
        if (childHeight>height) {
            height = childHeight;
        }
    }

    //Return highest point
    return height + 1;
}

如果节点没有子节点，这只会返回 1。否则，它获取所有孩子的最大高度并返回该数字加 1。

于 2013-09-14T02:13:00.263 回答