樹中最高總和的路徑

Question

我必須從根節點到葉節點找到最大總和。 我已經拿出了下面的節點，但它沒有給出正確的輸出。樹可以有兩個以上的子節點（它不是二叉樹）。

public static long findBestPath(Path path) { 
    long max = 0, sum = 0; 
    if (path.getChildren().size() == 0) 
     return path.getValue(); 
    else if (path.getChildren().size() == 1) 
     return path.getValue() + findBestPath(path.getChildren().get(0)); 
    else { 
     for (int i = 0; i < path.getChildren().size(); i++) { 
      sum = path.getChildren().get(i).getValue() + findBestPath(path.getChildren().get(i)); 
      if (sum > max) 
       max = sum; 
     } 
     return max; 
    } 
} 

我用另一種方法來解決我的問題。儘管知道正確的解決方案來尋找非二叉樹的最大和路徑是很好的。

Answer 1

好解釋，你可以從here

Answer 2

你的錯誤是指應該在這條線：

sum = path.getChildren().get(i).getValue() + findBestPath(path.getChildren().get(i));

你必須寫：

sum = path.getValue() + findBestPath(path.getChildren().get(i));

你也不要在中間需要「else if」，這是路徑只有一個對於孩子來說，只有一個孩子的「其他」作品也很好。

所以，你的代碼應該是這樣的：

public static long findBestPath(Path path) { 
    long max = 0, sum = 0; 
    if (path.getChildren().size() == 0) 
     return path.getValue(); 
    else { 
     for (int i = 0; i < path.getChildren().size(); i++) { 
      sum = path.getValue() + findBestPath(path.getChildren().get(i)); 
      if (sum > max) 
       max = sum; 
     } 
     return max; 
    } 
} 

我希望它的作品。

另一種解決方案，它返回的孩子（我）+孩子（我）的兒童的最大金額的總和（如果我理解你的權利），將是：

public static long findBestPath(Path path) { 
    long max = 0, sum = 0; 
    if (path.getChildren().size() == 0) 
     return 0; 
    else { 
     for (int i = 0; i < path.getChildren().size(); i++) { 
      sum = path.getChildren().get(i).getValue() + findBestPath(path.getChildren().get(i)); 
      if (sum > max) 
       max = sum; 
     } 
     return max; 
    } 
} 

都只有工作，如果所有的值都是正值。