计算非二叉树的高度

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列表。您只为最后一个孩子添加了count，这意味着您计算了树中最右边路径的高度（假设您的孩子列表中的最后一个孩子是最右边的孩子）。

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