java - 计算非二叉树的高度

Question

如何将用于查找二叉树高度的递归代码推广到非二叉树？我检查了Non-binary tree height 。但只有一个伪代码。到目前为止，我写的以下内容给了我错误的答案:

public static <MyType> int calculateHeight(MyTreeNode<MyType> r){
        if (r ==null)
            return -1;
        if (r.children.size()==0)
            return 0;
        int count=0;
        List<Integer> heights = new ArrayList<>(); 
        for (MyTreeNode<MyType> e : r.children)
            count = calculateHeight(e)+1;           
        heights.add(count);
        return max(heights);        
    }

Answer 1

您遇到了缺少大括号的问题。您应该将 count 添加到每个子项的 heights 列表中。您只为最后一个子项添加了计数，这意味着您计算了树中最右侧路径的高度(假设子项列表中的最后一个子项是最右侧的子项)。

public static <MyType> int calculateHeight(MyTreeNode<MyType> r){
    if (r ==null)
        return 0;
    if (r.children.size()==0)
        return 1;
    int count=0;
    List<Integer> heights = new ArrayList<>(); 
    for (MyTreeNode<MyType> e : r.children) {
        count = calculateHeight(e)+1;           
        heights.add(count);
    }
    return max(heights);        
}