二叉树中每个级别的平均值
问题描述:
我正在尝试查找二叉树中每个级别的平均值。我在做BFS。我正在尝试使用空节点来完成它。每当我找到一个虚拟节点时,这意味着我处于该级别的最后一个节点。我面临的问题是,我无法使用此功能在树中添加最后一级的平均值。有人能帮我吗?二叉树中每个级别的平均值
考虑范例[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;
}
}
答
看看这段代码,它执行每当你发现当前级别的结束标记:
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;
有一个新的边界情况需要注意的,这是发生了什么如果树是完全空的。我会让你弄清楚如何从这里出发。祝你好运!
答
我会用树的递归深度扫描。在每个节点上,我会将值推入具有一对的映射中。
我没有测试该代码,但它应该是沿线。
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
}