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. ノードに子が1つしかない場合、すべてのパスがその子を通過します。
  3. それ以外の場合、ノードには2つの子があります。次に、すべてのパスが2つの子のうちの1つを通過します。

ケース1の場合、最大値はそのノードの値でなければなりません。ケース2の場合、最大値はそのノードの値に、その子のmax-path-sumを加えたものです（そのパスは、唯一の子を介して親のパスに拡張されるため）。ケース3の場合、最大値は2つの子の最大max-path-sumです（最適なパスは2つの子の1つを通過する必要があり、親は子の最適なパスのどちらが優れているかを確認できるため）。

したがって、コードは本当に単純です。ここでは、を返すので、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 に答える