This problem looks busy at first, but the accepted solution is built around one steady invariant. For 637. Average of Levels in Binary Tree, the solution in this repository is mainly a two pointers solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are averageOfLevels, fillVectors.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
03Example 1:
04Input:
05 3
06 / \
07 9 20
08 / \
09 15 7
10Output: [3, 14.5, 11]
11Explanation:
12The 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].
13Note:
14The range of node's value is in the range of 32-bit signed integer.
15**/
16
17/**
18 * Definition for a binary tree node.
19 * struct TreeNode {
20 * int val;
21 * TreeNode *left;
22 * TreeNode *right;
23 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
24 * };
25 */
26 //Runtime: 24 ms, faster than 99.44% of C++ online submissions for Average of Levels in Binary Tree.
27//Memory Usage: 22.3 MB, less than 25.66% of C++ online submissions for Average of Levels in Binary Tree.
28class Solution {
29public:
30 vector<double> averageOfLevels(TreeNode* root) {
31 vector<double> ans;
32 queue<TreeNode*> q;
33 vector<int> levelVals;
34 int level = 0, levelCount = 1, nextLevelCount = 0;
35
36 q.push(root);
37
38 while(q.size()!=0){
39 TreeNode* cur = q.front();
40 q.pop();
41
42 levelVals.push_back(cur->val);
43
44 levelCount--;
45
46 if(cur->left!=NULL){
47 q.push(cur->left);
48 nextLevelCount++;
49 }
50
51 if(cur->right!=NULL){
52 q.push(cur->right);
53 nextLevelCount++;
54 }
55
56 if(levelCount==0){
57 levelCount = nextLevelCount;
58 nextLevelCount = 0;
59 level++;
60 double levelSum = accumulate(levelVals.begin(), levelVals.end(), 0.0);
61 ans.push_back(levelSum/levelVals.size());
62 levelVals.clear();
63 }
64 }
65
66 return ans;
67 }
68};
69
70/**
71Approach #1 Using Depth First Search [Accepted]
72Algorithm
73
74One of the methods to solve the given problem is to make use of Depth First Search. In DFS, we try to exhaust each branch of the given tree during the tree traversal before moving onto the next branch.
75
76To make use of DFS to solve the given problem, we make use of two lists countcount and resres. Here, count[i]count[i] refers to the total number of nodes found at the i^{th}i
77th
78 level(counting from root at level 0) till now, and res[i]res[i] refers to the sum of the nodes at the i^{th}i
79th
80 level encountered till now during the Depth First Search.
81
82We make use of a function average(t, i, res, count), which is used to fill the resres and countcount array if we start the DFS from the node tt at the i^{th}i
83th
84 level in the given tree. We start by making the function call average(root, 0, res, count). After this, we do the following at every step:
85
86Add the value of the current node to the resres(or sumsum) at the index corresponding to the current level. Also, increment the countcount at the index corresponding to the current level.
87
88Call the same function, average, with the left and the right child of the current node. Also, update the current level used in making the function call.
89
90Repeat the above steps till all the nodes in the given tree have been considered once.
91
92Populate the averages in the resultant array to be returned.
93
94The following animation illustrates the process.
95**/
96/**
97Complexity Analysis
98Time complexity : O(n).
99The whole tree is traversed once only.
100Here, nn refers to the total number of nodes in the given binary tree.
101
102Space complexity : O(h).
103resres and countcount array of size h are used.
104Here, h refers to the height(maximum number of levels) of the given binary tree.
105Further, the depth of the recursive tree could go upto hh only.
106**/
107
108//Runtime: 44 ms, faster than 5.57% of C++ online submissions for Average of Levels in Binary Tree.
109//Memory Usage: 22.5 MB, less than 16.81% of C++ online submissions for Average of Levels in Binary Tree.
110
111/**
112class Solution {
113public:
114 void fillVectors(TreeNode* cur, int level, vector<double>& sum, vector<int>& count){
115 if(cur==NULL) return;
116
117 if(level < sum.size()){
118 sum[level]+=cur->val;
119 count[level]+=1;
120 cout << cur->val << endl;
121 }else{
122 sum.push_back(cur->val);
123 count.push_back(1);
124 cout << cur->val << endl;
125 }
126
127 //DFS
128 fillVectors(cur->left, level+1, sum, count);
129 fillVectors(cur->right, level+1, sum, count);
130 }
131 vector<double> averageOfLevels(TreeNode* root) {
132 vector<double> ans;
133 vector<double> sum;
134 vector<int> count;
135
136 fillVectors(root, 0, sum, count);
137
138 for(int i = 0; i < sum.size(); i++){
139 ans.push_back(sum[i]/count[i]);
140 }
141 return ans;
142 }
143};
144**/
145
146/**
147Approach #2 Breadth First Search [Accepted]
148Another method to solve the given problem is to make use of a Breadth First Search. In BFS, we start by pushing the root node into a queuequeue. Then, we remove an element(node) from the front of the queuequeue. For every node removed from the queuequeue, we add all its children to the back of the same queuequeue. We keep on continuing this process till the queuequeue becomes empty. In this way, we can traverse the given tree on a level-by-level basis.
149
150But, in the current implementation, we need to do a slight modification, since we need to separate the nodes on one level from that of the other.
151
152The steps to be performed are listed below:
153
154Put the root node into the queuequeue.
155
156Initialize sumsum and countcount as 0 and temptemp as an empty queue.
157
158Pop a node from the front of the queuequeue. Add this node's value to the sumsum corresponding to the current level. Also, update the countcount corresponding to the current level.
159
160Put the children nodes of the node last popped into the a temptemp queue(instead of queuequeue).
161
162Continue steps 3 and 4 till queuequeue becomes empty. (An empty queuequeue indicates that one level of the tree has been considered).
163
164Reinitialize queuequeue with its value as temptemp.
165
166Populate the resres array with the average corresponding to the current level.
167
168Repeat steps 2 to 7 till the queuequeue and temptemp become empty.
169
170At the end, resres is the required result.
171
172The following animation illustrates the process.
173Time complexity : O(n).
174The whole tree is traversed atmost once.
175Here, n refers to the number of nodes in the given binary tree.
176
177Space complexity : O(m).
178The size of queuequeue or temptemp can grow upto atmost the maximum number of nodes at any level in the given binary tree.
179Here, m refers to the maximum mumber of nodes at any level in the input tree.
180**/
181
182/**
183class Solution {
184public:
185 vector<double> averageOfLevels(TreeNode* root) {
186 vector<double> ans;
187 queue<TreeNode*> q;
188
189 q.push(root);
190
191 while(q.size()!=0){
192 double levelSum = 0;
193 int levelCount = 0;
194 queue<TreeNode*> qNext;
195
196 while(q.size()!=0){
197 TreeNode* cur = q.front();
198 q.pop();
199
200 levelSum += cur->val;
201 levelCount++;
202
203 if(cur->left!=NULL){
204 qNext.push(cur->left);
205 }
206
207 if(cur->right!=NULL){
208 qNext.push(cur->right);
209 }
210 }
211 ans.push_back(levelSum*1.0/levelCount);
212 q = qNext;
213 }
214
215 return ans;
216 }
217};
218**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.