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 返回一个 (level, value) 对的列表，然后对它们求和。这在协同程序类型的语言中更有意义，但在 java 中会很奇怪。

显然，您可以在递归函数中采用策略，并使用要处理的显式节点堆栈来执行此操作。我的方式和你的方式之间的主要区别在于我的方式与树的高度成正比。你的内存与它的宽度成正比。

查看您的代码，该方法似乎很合理。我将重命名tempLevel为currentLevel，并且我倾向于将内部循环拉出到一个函数sumLevel中，该函数接受一个队列并返回一个 int 和一个队列（实际上队列将是一个参数，因为你只能返回一个值， grrr）。但它看起来还可以。

于 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

这种递归方法对我有用：

public int findMaxSumRootLeaf(TreeNode node,int currSum) {
    if(node == null)
        return 0;
    return Math.max(findMaxSumRootLeaf(node.leftChild,currSum)+node.data, findMaxSumRootLeaf(node.rightChild,currSum)+node.data);
}
于 2013-11-11T00:47:48.503 回答
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 回答