DFS & BFS solution w/ C++ & Python


  • 0
    Z

    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
    

Log in to reply
 

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