爪哇 - 通過二叉樹

我試圖通過一個二叉樹寫一個路徑的最大金額的方法路徑的最大金額：爪哇 - 通過二叉樹

public class ConsTree<T> extends BinaryTree<T> 
{ 
    BinaryTree<T> left; 
    BinaryTree<T> right; 
    T data; 

    public int maxSum() 
    { 
    } 
}

如圖所示，每棵樹包含左側和右側的樹以及泛型類型的數據。我對如何着手開始這件事感到困惑。如果有人能夠提供關於算法的外觀或者讓我朝着正確的方向提供幫助，那就太好了。謝謝。

來源

2012-10-14 user1547050

你嘗試過什麼了嗎？如果是這樣，你嘗試了什麼？如果不是，什麼阻止你嘗試？ – nneonneo

也請記住，泛型可能不具有可比性。您應該使用'T extends Comparable'來確保類型具有可比性。 – nneonneo

我想過要經過樹中的每一條路徑，然後讓它跟蹤最大的一條路徑，但我不確定我會怎麼做，因爲這個方法是遞歸的。 – user1547050

遞歸思考的方法是考慮這些情況。在我們的例子中，我們看一個單一的節點，並且可以決定有什麼樣的路徑：

如果該節點沒有孩子，那麼唯一的路徑是單路徑（本身由該節點的）。
如果該節點只有一個孩子，則所有路徑都會經過該孩子。
否則，節點有兩個孩子。然後，所有路徑都通過其兩個孩子中的一個。

在情況1中，最大值必須是該節點的值。在情況2中，最大值是該節點的值，加上其子的最大路徑總和（因爲該路徑通過唯一的子節點擴展到父路徑）。在情況3中，最大值是其兩個孩子的最大路徑總和（因爲最佳路徑必須通過兩個孩子中的一個，並且父母可以看到哪個孩子的最佳路徑更好）。

因此，代碼非常簡單。在這裏，由於您返回int，因此我將假設T = int。

public int maxSum() { 
    /* case 1 */ 
    if(left == null && right == null) 
     return data; 

    /* case 2 */ 
    if(right == null) 
     return data + left.maxSum(); 
    else if(left == null) 
     return data + right.maxSum(); 

    /* case 3 */ 
    return Math.max(data + left.maxSum(), data + right.maxSum()); 
}

來源

2012-10-14 07:41:58 nneonneo

您假設最大總和路徑必須經過根，但我認爲這不是必需的。可能有一條路徑的最大和不經過根。 – Pan

private static int max = Integer.MIN_VALUE; 

public static int maxPathSum(TreeNode root) { 
    int rd = dfs(root); 
    return rd > max ? rd : max; 
} 

// close paths: 
// 1 left leaf 
// 2 right leaf 
// 3 left + root + right 
// 
// open paths: 
// 4 root 
// 5 left + root 
// 6 right + root 
private static int dfs(TreeNode root) { 
    if (root.left == null && root.right == null) { 
     return root.val; 
    } 
    if (root.left == null && root.right != null) { 
     int rPathMax = dfs(root.right); 
     max = rPathMax > max ? rPathMax : max; 
     return Math.max(root.val, rPathMax + root.val); 
    } 
    if (root.right == null && root.left != null) { 
     int lPathMax = dfs(root.left); 
     max = lPathMax > max ? lPathMax : max; 
     return Math.max(root.val, lPathMax + root.val); 
    } 
    int lPathMax = dfs(root.left); 
    int rPathMax = dfs(root.right); 
    int closePathMax = lPathMax + rPathMax + root.val; 

    int innerMax = Math.max(closePathMax, Math.max(lPathMax, rPathMax)); 
    max = innerMax > max ? innerMax : max; 
    return Math.max(root.val, Math.max(lPathMax + root.val, rPathMax + root.val)); 
}

來源

2016-02-18 01:41:38

爪哇 - 通過二叉樹

回答

相關問題