Q:
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input:
3
/ \
9 20
/ \
15 7
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.
A:
借用了两个数组,记录sum , and count;
/** * 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<double> averageOfLevels(TreeNode* root) { vector<double> res; vector<int> count; helper(root, res, count, 1); for(int i =0;i<count.size(); i++) { res[i] /= count[i]; } return res; } private: void helper(TreeNode* root, vector<double> & res, vector<int> &count, int depth) { if(!root) return; if(res.size() < depth) { count.push_back(0); res.push_back(0); // at most need one layer } res[depth-1] += root->val; count[depth-1] ++; helper(root->left, res, count, depth+1); helper(root->right, res,count, depth+1); } };
借用了两个数组,记录sum , and count;
No comments:
Post a Comment