LeetCode637. Average of Levels in Binary Tree

LeetCode

字数统计: 788阅读时长: 4 min

 2020/03/04   Share

637. Average of Levels in Binary Tree

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.

/**
 * DFS Solution.
 * 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) {
        if(root == nullptr) return {};
        vector<pair<long long, int>> sum_count;
        preorder(root, 0, sum_count);
        vector<double> ans;
        for( const auto& p : sum_count){
            ans.push_back( static_cast<double>(p.first)/p.second );
        }
        return ans;
    }
private:
    void preorder( TreeNode* root, int depth,  vector<pair<long long, int>>& sum_count){
        if(root == nullptr) return;
        if(depth >= sum_count.size()) sum_count.push_back({0,0});
        sum_count[depth].first += root->val;
        ++sum_count[depth].second;
        preorder(root->left, depth+1, sum_count);
        preorder(root->right, depth+1, sum_count);
    }
};

note：pair using & explain

//CPP program to illustrate pair STL
#include <iostream>
#include <utility>
using namespace std;

int main()
{
    pair <int, char> PAIR1 ;

    PAIR1.first = 100;
    PAIR1.second = 'G' ;

    cout << PAIR1.first << " " ; 	//visit the first value;
    cout << PAIR1.second << endl ; 	//visit the second value;

    return 0;
}
//out:
//100G

//standard initializtion
pair <data_type1, data_type2> pair_name(value1, value2);
//initialization can be also omitted
pair <data_type1, data_type2> pair_name;

Time Complexity: O(N) , N is the nodes number of Tree

Space Complexity: O(H) , H is the height of Tree

/**
 * BFS Solution.
 * 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> ans;
      vector<TreeNode*> curr, next;
      curr.push_back(root);
      while(!curr.empty()){		//when curr point is null, it means all over.
        long long sum = 0;
        for( const auto& node : curr ){
          sum += node->val;
          if(node->left) next.push_back(node->left);
          if(node->right) next.push_back(node->right);
        }
        ans.push_back(static_cast<double>(sum)/curr.size());
        curr.swap(next);	//swap curr with next
        next.clear();
      }
  		return ans;

    }
};

Time Complexity: O(N) , N is the nodes number of Tree

Space Complexity: O(M) , M is the maximum of every level to the Tree

Solution version using Java

/**
 * java
 * DFS
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        List<Integer> count = new ArrayList<>();
        if(root == null) return ans;
        getSumOfLevel(root, 0, ans, count);
        for(int i = 0; i < ans.size(); i++){
            ans.set(i, ans.get(i)/count.get(i));
        }
        return ans;
    }

    public static void getSumOfLevel(TreeNode t, int depth, List < Double > ans, List < Integer > count){
        if(t == null) return;
        if(depth < ans.size()){
            ans.set(depth, ans.get(depth)+t.val);
            count.set(depth, count.get(depth)+1);
        }else{
            ans.add(t.val*1.0);
            count.add(1);
        }
        getSumOfLevel(t.left, depth+1, ans, count);
        getSumOfLevel(t.right, depth+1, ans, count);
    }
}

/**
 * java BFS
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            long sum = 0;
            int count = 0;
            Queue<TreeNode> temp = new LinkedList<>();
            while(!queue.isEmpty()){
                TreeNode t = queue.remove();
                sum += t.val;
                count++;
                if(t.left != null ){
                    temp.add(t.left);
                }
                if(t.right != null ){
                    temp.add(t.right);
                }
            }
            queue = temp;
            ans.add(((double)sum)/count);
        }
        return ans;
    }
}

Next Post

LeetCode628. Maximum Product of Three Numbers
Previous Post

LeetCode463. Island Perimeter

CATALOG

1. 637. Average of Levels in Binary Tree
2. Example 1:
3. Explanation:

