题目地址
典型的BFS了，只需要在遍历当前层级的时候记录下结点个数和值的累加和就好了。
List<Double> result = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
- 注意new后面的具体数据类型：
List<Double> = new ArrayList
Queue<TreeNode> = new LinkedList<>()
int n = q.size();
double sum = 0.0;
for(int i = 0; i < n; i++) {
- q.size()是什么操作？
记录每一层node数量.
记住LinkedList的大小是用size()
for (int i = 0; i < layerSize; i++ ) {
TreeNode tempNode = q.poll();
sum += tempNode.val;
if (node.left != null) q.add(tempNode.left);
if (node.right != null) q.add(tempNode.right);
ArrayList, LinkedList - List添加元素都是add
q.add(root);
result.add(sum / levelSize)for loop 里初始化int又忘记了
for (int i = 0; i < layerSize; i++ ) {
- node left, right 要先判断非null了以后再确定add
for (int i = 0; i < layerSize; i++ ) {
TreeNode tempNode = q.poll();
sum += tempNode.val;
if (node.left != null) q.add(tempNode.left);
if (node.right != null) q.add(tempNode.right);
102. Binary Tree Level Order Traversal
忘记Base case了！
if (root == null) return result;
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
Queue<TreeNode> q = new LinkedList<>();
if (root == null) return result;
q.offer(root);
while(!q.isEmpty()){
int n = q.size();
List<Integer> tempList = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode tempNode = q.poll();
tempList.add(tempNode.val);
if(tempNode.left != null) {q.offer(tempNode.left);}
if(tempNode.right != null) {q.offer(tempNode.right);}
}
result.add(tempList);
}
return result;
}
下一个目标是弄清楚：Top down和Bottom up
理解：
Bottom up - 是指不到最下面的叶节点，不会return（触底后反弹 - 下面得到的值一层层带回去）
Top down
