1

我正在尝试为通过二叉树的路径的最大总和编写一种方法：

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

    public int maxSum() 
    {
    }
}

如图所示，每棵树在其左侧和右侧都包含一棵树，以及一个泛型类型的数据。我对如何开始这个有点困惑。如果有人可以就算法的外观提供帮助或让我朝着正确的方向前进，那就太好了。谢谢。

4

2 回答 2

2

递归思考的方法是考虑案例。在我们的例子中，我们查看单个节点并可以决定它有哪些路径：

  1. 如果节点没有子节点，则唯一的路径是单例路径（由该节点本身组成）。
  2. 如果节点只有一个子节点，则所有路径都通过该子节点。
  3. 否则，该节点有两个孩子。然后，所有路径都通过它的两个孩子之一。

在情况 1 中，最大值必须是该节点的值。在情况 2 中，最大值是该节点的值，加上其子节点的最大路径和（因为该路径通过唯一的子节点扩展到父节点的路径）。在情况 3 中，最大值是它的两个孩子的最大 max-path-sum（因为最好的路径必须经过两个孩子中的一个，并且父母可以看到孩子的最佳路径中哪一个更好）。

因此，代码非常简单。在这里，由于您返回一个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-14T07:41:58.647 回答
0 
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-18T01:41:38.027 回答