solution 1: 比较低效

//url:https://leetcode.com/problems/average-of-levels-in-binary-tree/description/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

struct NodeSum{
    long sum;//该层级的和
    int num;//该层级节点数量
    NodeSum():sum(0),num(0){        
    }
};

class Solution {
public:
    vector averageOfLevels(TreeNode* root) {
        map sum;
        calLevelSum(root,0,sum);
        vector result;
        for(map::iterator it=sum.begin();it!=sum.end();it++){
            result.push_back(1.0*it->second.sum/it->second.num);
        }
        return result;
    }
    void calLevelSum(TreeNode* root,int level,map& sum){
        if(!root)
            return;
        map::iterator it=sum.find(level);
        if(it==sum.end()){
            NodeSum s;
            s.sum=root->val;
            s.num=1;
            sum[level]=s;
        }else{
            it->second.sum+=root->val;
            it->second.num++;
        }
        calLevelSum(root->left,level+1,sum);
        calLevelSum(root->right,level+1,sum);
    }
};

solution 2:也是比较低效,只是在 calLevelSum 里面,减掉了find操作

//url:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

struct NodeSum{
    long sum;//该层级的和
    int num;//该层级节点数量
    NodeSum():sum(0),num(0){        
    }
};

class Solution {
public:
    vector averageOfLevels(TreeNode* root) {
        map sum;
        calLevelSum(root,0,sum);
        vector result;
        for(map::iterator it=sum.begin();it!=sum.end();it++){
            result.push_back(1.0*it->second.sum/it->second.num);
        }
        return result;
    }
    void calLevelSum(TreeNode* root,int level,map& sum){
        if(!root)
            return;
        sum[level].sum+=root->val;
        sum[level].num+=1;
        calLevelSum(root->left,level+1,sum);
        calLevelSum(root->right,level+1,sum);
    }
};

solution 3: 高效！

//url:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


class Solution {
public:
    vector averageOfLevels(TreeNode* root) {
        vector sum;
        vector num;
        calLevelSum(root,0,sum,num);
        vector result;
        for(int i=0;i&sum,vector& num){
        if(!root)
            return;
        if(level==sum.size()){
            sum.push_back(root->val);
            num.push_back(1);
        }else{
            sum[level]+=root->val;
            num[level]++;
        }        
        calLevelSum(root->left,level+1,sum,num);
        calLevelSum(root->right,level+1,sum,num);
    }
};