ProblemSolving/AverageOfLevelsInBinaryTree.java at master · yovrer/ProblemSolving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

import java.util.*;
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author rn-sshawish
 */
public class AverageOfLevelsInBinaryTree {
    TreeMap<Integer, Data> levelSum = new TreeMap<>();

//     public List<Double> averageOfLevels(TreeNode root) {
//
//         List<Double> output = new ArrayList<>();
//         processTree(root, 0);
//         for (Map.Entry<Integer, Data> double1 : levelSum.entrySet()) {
//
//             output.add(double1.getValue().sum/double1.getValue().count);
//
//         }
//
//
//         return output;
//    }

    public List<Double> averageOfLevels(TreeNode root) {
    List<Double> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();

    if(root == null) return result;
    q.add(root);
    while(!q.isEmpty()) {
        int n = q.size();
        double sum = 0.0;
        for(int i = 0; i < n; i++) {
            TreeNode node = q.poll();
            sum += node.val;
            if(node.left != null) q.offer(node.left);
            if(node.right != null) q.offer(node.right);
        }
        result.add(sum / n);
    }
    return result;
}

     public void processTree (TreeNode root , int level){
         if (root == null) {

             return;

         }

        Data data = levelSum.get(level);

         if (data == null) {

             data = new Data();

             data.sum = root.val;

             data.count = 1;

             levelSum.put(level, data);

         }else{

             data.sum += root.val;

             ++data.count;

         }

         processTree(root.right, level + 1 );

         processTree(root.left, level + 1 );


     }

}

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }


class Data {
    double sum ;

    double count;
}