Average of Levels in Binary Tree

SGiven a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input:

Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
The range of node’s value is in the range of 32-bit signed integer.

描述：

给定一个非空的二叉树，返回每个级别的节点的平均值的数组

例1： 输入： 3 / \ 9 20
/ \ 15 7
输出：[ 3，14.5，11 ] 解释： 0级节点的平均值为3，第1级为14.5，第2级为11。因此返回[ 3，14.5，11 ]。
注： 节点值的范围在32位有符号整数的范围内。

分析

层次遍历：

1.对于不为空的结点，先把该结点加入到队列中
2.从队列中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中
3.重复以上操作直到队列为空

时间复杂度

时间复杂度 O(n) n为节点个数

Java

class Solution {  
    public List<Double> averageOfLevels(TreeNode root) {
         if (root == null){
            return null;
        }

        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        LinkedList<Double> numbers = new LinkedList<Double>();
        TreeNode currentNode = new TreeNode(0);

        //第一层
        list.add(root);

        double sumOfLevel = 0;
        while(!list.isEmpty()){
            int len = list.size();
            for(int i = 0;i<len;i++){
                //对当前队列中所有元素操作（出队列并加入他的两个子节点）
                currentNode = list.poll();
                sumOfLevel += currentNode.val;
                if(currentNode.left != null){
                    list.offer(currentNode.left);   
                }
                if(currentNode.right != null){
                    list.offer(currentNode.right);   
                }
            }
          double ave = sumOfLevel / (double)len;
            sumOfLevel = 0;
          numbers.add(ave);

        }

        return numbers;
    }
}

C++

class Solution {  
public:  
    vector<double> averageOfLevels(TreeNode* root) {
         queue<TreeNode*> mqueue;
        vector<double> ret;
        if(!root)
            return {};
        mqueue.push(root);
        while(mqueue.size())
        {
            int n = mqueue.size();
            long sum = 0;
            for(int i = 0; i < n; i++)
            {
                TreeNode* r = mqueue.front();
                sum += r->val;
                if(r->left)
                    mqueue.push(r->left);
                if(r->right)
                    mqueue.push(r->right);
                mqueue.pop();
            }
            ret.push_back((double)sum / n);
        }
        return ret;  
    }
};

Swift

class Solution {  
    func averageOfLevels(_ root: TreeNode?) -> [Double] {

      guard let root = root else { return [] }

        var parentsArray = [TreeNode]()
        var averageArray = [Double]()

        parentsArray.append(root)

        while !parentsArray.isEmpty {

            var childrenArray = [TreeNode]()
            var total = 0.0
            var count = 0.0

            for currentNode in parentsArray {

                total += Double(currentNode.val)
                count += 1

                if currentNode.left != nil {
                    childrenArray.append(currentNode.left!)
                }
                if currentNode.right != nil {
                    childrenArray.append(currentNode.right!)
                }
            }

            averageArray.append(total/count)
            parentsArray = childrenArray

        }
        return averageArray
    }
}

本题来自:leetCode