# DFS & BFS solution w/ C++ & Python

• python dfs:

``````class Solution(object):
def averageOfLevels(self, root):
def dfs(node, height):
if node:
if height > len(levelsum):
levelsum.append([0.0, 0.0])
levelsum[height-1][0] += node.val
levelsum[height-1][1] += 1
dfs(node.left, height + 1)
dfs(node.right, height + 1)
levelsum = []
dfs(root, 1)
return [val / count for val, count in levelsum]

# Runtime: 105 ms
``````

python bfs:

``````class Solution(object):
def averageOfLevels(self, root):
q = collections.deque([root])
result = []
while q:
val, n = 0, len(q)
for i in xrange(n):
node = q.popleft()
val += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(val / float(n))
return result

# Runtime: 75 ms
``````

c++ dfs:

``````class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> sum, count;
dfs(root, 1, sum, count);
for ( int i = 0; i < sum.size(); ++i )
sum[i] /= count[i];
return sum;
}

void dfs(TreeNode * root, int height, vector<double> & sum, vector<double> & count) {
if ( root ) {
if ( height > sum.size() ) {
sum.push_back(0);
count.push_back(0);
}
sum[height-1] += root->val;
++count[height-1];
dfs(root->left, height + 1, sum, count);
dfs(root->right, height + 1, sum, count);
}
}
};

// Runtime: 13 ms
``````

c++ bfs:

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

// Runtime: 15 ms
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.