原题地址（简单）

此题是非常简单的二叉树递归题目，可以用深度优先搜索和广度优先搜索来做。

方法1—深度优先搜索

深搜需要用递归，所以要先把每一层的总和都算出来，再除以每一层的结点数。
所以需要两个 veotor ，来存储每一层的总和，每一层的结点数。

  1. class Solution {
  2. public:
  3.     vector<double> sums, nums;  // sums存储每层的总和，nums存储每层的总结点数
  4.     vector<double> averageOfLevels(TreeNode* root) {
  5.         dfs(root, 0);
  7.         for(int i=0; i<sums.size(); i++)
  8.             sums[i] /= nums[i];
  9.         return sums;
  10.     }
  12.     void dfs(TreeNode* root, int level){
  13.         if(!root)   return;
  14.         int len = sums.size();
  15.         if(level <= len-1){
  16.             sums[level] += root->val;
  17.             nums[level]++;
  18.         }
  19.         else{
  20.             sums.push_back(1.0 * root->val);
  21.             nums.push_back(1);
  22.         }
  23.         if(root->left)  dfs(root->left, level+1);
  24.         if(root->right)  dfs(root->right, level+1);
  25.     }
  26. };

方法2—广度优先搜索

递归的性质不太适合广度优先搜索，所以广搜一般用栈或队列来模拟。


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