【0.5对】 Average of Levels in Bina

https://leetcode.com/problems/average-of-levels-in-binary-tree/

日期	是否一次通过	comment
2019-01-16 19:27	非递归一次通过，递归方法遭遇int溢出。实际上sum应该保存double类型，而不是int	分层遍历BFS

image.png

（来源： https://leetcode.com/problems/average-of-levels-in-binary-tree/）

1. 本质上就是个遍历啊
2. 非递归方法里，null永远不要存进stack or queue

递归

class NodeSum {
    double sum;
    int num;
}

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> avgList = new ArrayList<>();
        if(root == null) {
            return avgList;
        }
        
        List<NodeSum> nodeSumList = new ArrayList<>();
        helper(root, nodeSumList, 0);
        sumArray(nodeSumList, avgList);
        return avgList;
    }
    
    private void helper(TreeNode root, List<NodeSum> nodeSumList, int level) {
        
        if(root == null) {
            return;
        }
        if(level >= nodeSumList.size()) {
            NodeSum nodeSum = new NodeSum();
            nodeSum.sum = root.val;
            nodeSum.num = 1;
            nodeSumList.add(nodeSum);
        } else {
            NodeSum nodeSum = nodeSumList.get(level);
            nodeSum.sum += root.val;
            nodeSum.num += 1;
        }
        
        helper(root.left, nodeSumList, level+1);
        helper(root.right, nodeSumList, level+1);
    }
    
    private void sumArray(List<NodeSum> nodeSumList, List<Double> avgList) {
        if(nodeSumList == null) {
            return;
        }
        for(NodeSum nodeSum : nodeSumList) {
            avgList.add(nodeSum.sum / nodeSum.num);
        }
    }
}

非递归

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> avgList = new ArrayList<>();
        if(root == null) {
            return avgList;
        }
        
        Queue<TreeNode> nodeQ = new LinkedList<>();
        nodeQ.offer(root);
        while(!nodeQ.isEmpty()) {
            int length = nodeQ.size();
            double tempSum = 0.;
            for(int i=0; i<length; i++) {
                TreeNode node = nodeQ.poll();
                
                tempSum += node.val;
                if(node.left != null) {
                    nodeQ.offer(node.left);
                }
                if(node.right != null) {
                    nodeQ.offer(node.right);
                }

            }
            avgList.add(tempSum/length);
        }
        return avgList;
    }