二叉樹最大總和水平 - 更好的設計？

Question

我已經編寫了一個代碼，用於在具有最大元素總和的二叉樹中查找等級。我有幾個問題。

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; 
   } 
   

   }

Answer 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，我傾向於將內部循環拉出到函數sumLevel中，該函數接受一個隊列並返回一個int和一個隊列（實際上隊列將是一個參數除外，因爲您只能返回一個值，grrr）。但現在看起來沒問題。

Answer 2

你確定元素將所有非負？

我會讓它像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; 
    }    

} 

Answer 3

這取決於你的樹木多少個節點，並有多深，他們是。由於您正在執行breadth first search，因此您的隊列將佔用O（n）內存空間，這對大多數應用程序來說都是正常的。

以下溶液具有O（升）空間複雜度和和O（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並掃描返回的列表以查找最大值。

Answer 4

這個遞歸方法適用於我：

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); 
} 

Answer 5

可以表示使用隊列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 
    } 
}