1

-- java -- ツリー用

     5
  4     3
30  5

「最大トラック」を見つける必要があるため、このツリーでは 39 (5​​+4+30)

私はそれを行う関数が必要です (複雑さ O(n)) 誰かが私を助けることができますか?

public static int GetTreePath(BinTreeNode<Integer> t){
        if (t==null)
            return 0;

        if (t.IsLeve()){
            return t.getInfo();
        }else{
            GetTreePath(t.getLeft());
            GetTreePath(t.getRight());
        }
        return t.getInfo();
    }
4

2 に答える 2

0

可能な両方のサブツリーを最大限に取得するために、コードを少し変更しました。

public static int GetTreePath(BinTreeNode<Integer> t){
    if (t==null)
        return 0;

    if (t.IsLeve()){
        return t.getInfo();
    }else{
        return Math.max(
            GetTreePath(t.getLeft()), 
            GetTreePath(t.getRight()) 
            ) + t.getInfo();
    }
}
于 2012-05-20T07:29:03.163 に答える
0

DP ソリューションがあります。

F(i) = max(F(child) + value(i))

calculate(f)葉から根まで、または再帰して保存しますf(i)

于 2012-05-20T07:33:22.057 に答える