計算非二叉樹的高度

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