计算非二叉树的高度

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

您有缺少牙套的问题。您应该为每个 children 添加 count 到 heights 列表。您只为最后一个 child 添加了 count，这意味着您计算了树中 right-most 路径的高度（假设您的 child 中的最后一个 child ]ren 列表是 right-most child).

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);        
}

计算非二叉树的高度

calculate height of none-binary tree

java

tree