1

要素の最大合計を持つバイナリ ツリーでレベルを見つけるためのコードを作成しました。いくつかの質問を聞きたいんです。

  1. 良いデザインですか？- 2 つのキューを使用しましたが、両方のキューに格納される要素の総数は n 未満になります。だから大丈夫だと思います。

  2. より良いデザインはありますか？

    public class MaxSumLevel {  
public static int findLevel(BinaryTreeNode root) {      
    Queue mainQ = new Queue();
    Queue tempQ = new Queue();
    int maxlevel = 0;
    int maxVal = 0;
    int tempSum = 0;
    int tempLevel = 0;
    if (root != null) {
        mainQ.enqueue(root);
        maxlevel = 1;
        tempLevel = 1;
        maxVal = root.getData();
    }           
    while ( !mainQ.isEmpty()) {         
        BinaryTreeNode head = (BinaryTreeNode) mainQ.dequeue();
        BinaryTreeNode left = head.getLeft();
        BinaryTreeNode right = head.getRight();
        if (left != null) {
            tempQ.enqueue(left);
            tempSum = tempSum + left.getData();
        }
        if (right != null) {
            tempQ.enqueue(right);
            tempSum = tempSum + right.getData();
        }           
        if (mainQ.isEmpty()) {
            mainQ = tempQ;
            tempQ = new Queue();
            tempLevel ++;
            if (tempSum > maxVal) {
                maxVal = tempSum;
                maxlevel = tempLevel;
                tempSum = 0;
            }               
        }           
    }
    return maxlevel;
}

    }

4

5 に答える 5

1

ツリーのノード数とその深さによって異なります。幅優先検索を実行しているため、キューはO(n)メモリ スペースを使用しますが、これはほとんどのアプリケーションで問題ありません。

次のソリューションには、O(l)空間の複雑さとO(n)時間の複雑さがあります ( lはツリーの深さとその頂点の数nです)。

public List<Integer> levelsSum(BinaryTreeNode tree) {
    List<Integer> sums = new ArrayList<Integer>()
    levelsSum(tree, sums, 0);
    return sums;
}
protected void levelsSum(BinaryTreeNode tree, List<Integer> levelSums, int level) {
    if (tree == null)
        return;
    // add new element into the list if needed
    if (level.size() <= level)
        levelSums.add(Integer.valueOf(0));
    // add this node's value to the appropriate level
    levelSums.set(level, levelSums.get(level) + tree.getData());
    // process subtrees
    levelSum(tree.getLeft(),  levelSums, level + 1);
    levelSum(tree.getRight(), levelSums, level + 1);
}

次に、ツリーを呼び出しlevelsSum、返されたリストをスキャンして最大値を見つけます。

于 2012-08-13T08:22:07.617 に答える
1

私は再帰が好きです（注、テストされていないコード）：

public static int maxLevel(BinaryTreeNode tree) {    
    ArrayList<Integer> levels = new ArrayList<Integer>();
    findLevels(tree, 0, levels);
    // now just return the index in levels with the maximal value.
    // bearing in mind that levels could be empty.
}
private static void findLevels(BinaryTreeNode tree, int level,
                                  ArrayList<Integer> levels) {
    if (tree == null) {
        return;
    }
    if (levels.length <= level) {
        levels.add(0);
    }
    levels.set(level, levels.get(level) + tree.getData());
    findLevels(tree.getLeft(), level+1, levels);
    findLevels(tree.getRight(), level+1, levels);
}

ガベージ コレクターに対して本当に意地悪をしているとしたら、findLevels が (レベル、値) ペアのリストを返して、それらを合計するようにします。これは、コルーチンのような言語ではより理にかなっていますが、Java では奇妙です。

明らかに、再帰関数で戦略を取り、処理するノードの明示的なスタックでそれを行うことができます。私の方法とあなたの方法の主な違いは、私の方法はツリーの高さに比例してメモリを消費することです。あなたのものは、その幅に比例してメモリを消費します。

あなたのコードを見ると、このアプローチはかなり合理的です。名前を に変更tempLevelしcurrentLevel、内側のループを、キューを受け取って int とキューを返す関数に引き抜く傾向がsumLevelあります (ただし、実際にはキューは引数になります。返せる値は 1 つだけなので、うーん）。でもそのままでいいらしい。

于 2012-08-13T08:25:28.210 に答える
0

すべての要素が負でないことを確信していますか?

のように呼び出し可能にしnew MaxSumLevel(root).getLevel()ます。そうでなければ、時々 maxSum を返さなければならないとき、あなたはどうしますか?

これを 2 つのネストされたループとして構成します。

while(!mainQ.isEmpty()){
     while(!mainQ.isEmpty()){
        BinaryTreeNode head = (BinaryTreeNode) mainQ.dequeue();
        BinaryTreeNode left = head.getLeft();
        BinaryTreeNode right = head.getRight();
        if (left != null) {
            tempQ.enqueue(left);
            tempSum = tempSum + left.getData();
        }
        if (right != null) {
            tempQ.enqueue(right);
            tempSum = tempSum + right.getData();
        }
     }
     mainQ = tempQ;
     tempQ = new Queue();
     tempLevel ++;
     if (tempSum > maxVal) {
         maxVal = tempSum;
         maxlevel = tempLevel;
         tempSum = 0;
     }               

}
于 2012-08-13T07:54:31.777 に答える
0

キューを使用してレベルの終わりを表しnull、各レベルの最大合計を計算できます。

public int maxLevelSum(BinaryTreeNode root) {
    if (root == null)                 //if empty tree
        return 0;
    else {
        int current_sum = 0;          
        int max_sum = 0;
        Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();       //initialize a queue
        queue.offer(root);  //add root in queue
        queue.offer(null);  // null in queue represent end of a level
        while (!queue.isEmpty()) {
            BinaryTreeNode temp = queue.poll();         
            if (temp != null) {
                if (temp.getLeft() != null)                  //if left is not null
                    queue.offer(temp.getLeft());
                if (temp.getRight() != null)
                    queue.offer(temp.getRight());            //if right is not null
                current_sum = current_sum + temp.getData();  //add to level current level sum
            } else {                                         // we reached end of a level
                if (current_sum > max_sum)                   //check if cuurent level sum is greater than max
                    max_sum = current_sum;
                current_sum = 0;                            //make current_sum=0 for new level
                if (!queue.isEmpty())                                  
                    queue.offer(null);                      //completion of a level
            }
        }
        return max_sum;                                     //return the max sum
    }
}
于 2016-01-14T22:47:37.700 に答える