バイナリツリーの各レベルの平均

Question

バイナリツリーの各レベルの平均を求めようとしています。私はBFSをやっています。私はnullノードを使用してそれをしようとしています。ダミーノードを見つけると、そのレベルの最後のノードにいることを意味します。私が直面している問題は、これを使ってツリーの最後のレベルの平均を追加できないということです。誰か助けてくれますか？

例[3,9,20,15,7] [3.00000,14.50000]と出力されています。 15と7 で最後のレベルの平均値を取得しないと、ここに私のコード

/** 
* Definition for a binary tree node. 
* public class TreeNode { 
*  int val; 
*  TreeNode left; 
*  TreeNode right; 
*  TreeNode(int x) { val = x; } 
* } 
*/ 

public class Solution { 
public List<Double> averageOfLevels(TreeNode root) { 
    List<Double> list = new ArrayList<Double>(); 
    double sum = 0.0; 
    Queue<TreeNode> q = new LinkedList<TreeNode>(); 
    TreeNode temp = new TreeNode(0); 
    q.offer(root); 
    q.offer(temp); 
    int count = 0; 
    while(!q.isEmpty()){ 
     root = q.poll(); 
     sum += root.val; 

     if(root != temp) 
     { 
      count++; 
      if(root.left != null){ 
       q.offer(root.left); 
      } 
      if(root.right != null){ 
       q.offer(root.right); 
      } 
     } 
     else 
     { 
      if(!q.isEmpty()){ 
      list.add(sum/count); 
      sum = 0; 
      count = 0; 
      q.add(temp);   
      } 
     } 

    } 
    return list; 
    } 
} 

Answer 1

あなたが現在のレベルの終わりのためのマーカーを見つけるたび実行する、このコードを見てみましょう：

if(!q.isEmpty()){ 
     list.add(sum/count); 
     sum = 0; 
     count = 0; 
     q.add(temp);   
    } 

をこのif文はあなたが終わったかどうかをチェックするように設計されているようですツリーの最後の行。キューに次のレベルに対応するエントリがないことに気づいて検出できます。その場合、ダミーノードを待ち行列に追加したくない（無限ループを引き起こす）のは間違いないが、完了した行の平均値も計算していないことに注意してください。この問題を解決するには

は、あなたが独立してキューを再シードの最後の行の平均値を計算したいと思う、次のように：

if(!q.isEmpty()){ 
     q.add(temp);   
    } 

    list.add(sum/count); 
    sum = 0; 
    count = 0; 

に注意する新しいエッジケースがあります、それは何が起こるかですツリーが完全に空の場合。ここから進める方法を考えさせます。がんばろう！

Answer 2

私は木の再帰的なディープスキャンを使用することになります。各ノードで、値をペアのあるマップにプッシュします。

私はコードをテストしませんでしたが、行に沿っている必要があります。

void scan(int level, TreeNode n, Map<Integer, List<Integer> m) { 
    List l = m.get(level); if (l==null) { 
    l = new ArrayList(); 
    m.put(level, l); 
    } 
    l.add(n.val); 
    int nextLevel = level + 1; 
    if (n.left != null) scan(nextLevel, n.left, m); 
    if (n.right != null) scan(nextLevel, n.right, m); 
} 

スキャンが完了したら、各レベルの平均を計算することができます。

for (int lvl in m.keyset()) { 
    List l = m.get(lvl); 
    // MathUtils.avg() - it is obvious what it should be 
    double avg = MathUtils.avg(l); 
    // you code here 
}