forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
MostFrequentSubtreeSum.java
107 lines (104 loc) · 3.17 KB
/
MostFrequentSubtreeSum.java
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
100
101
102
103
104
105
106
107
/*https://binarysearch.com/problems/Most-Frequent-Subtree-Sum*/
/*https://leetcode.com/problems/most-frequent-subtree-sum/*/
import java.util.*;
/**
* public class Tree {
* int val;
* Tree left;
* Tree right;
* }
*/
class Solution {
HashMap<Integer,Integer> map;
public int solve(Tree root) {
if (root == null) return -1;
map = new HashMap<Integer,Integer>();
int sum = recur(root);
map.put(sum, map.containsKey(sum) ? (Integer)map.get(sum)+1 : 1);
int maxSum = Integer.MIN_VALUE, maxSumKey = -1;
for (Map.Entry entry : map.entrySet())
{
if ((Integer)entry.getValue() > maxSum)
{
maxSum = (Integer)entry.getValue();
maxSumKey = (Integer)entry.getKey();
}
}
return maxSumKey;
}
public int recur(Tree root)
{
if (root == null) return 0;
if (root.left == null && root.right == null)
{
map.put(root.val,map.containsKey(root.val) ? (Integer)map.get(root.val)+1 : 1);
return root.val;
}
int sum = recur(root.left) + recur(root.right) + root.val;
map.put(sum,map.containsKey(sum) ? (Integer)map.get(sum)+1 : 1);
return sum;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
ArrayList<Integer> result;
HashMap<Integer,Integer> map;
int max;
public int[] findFrequentTreeSum(TreeNode root) {
result = new ArrayList<Integer>();
map = new HashMap<Integer,Integer>();
max = Integer.MIN_VALUE;
int i = 0;
findSum(root);
int[] arr = new int[result.size()];
for (Integer val : result)
arr[i++] = val;
return arr;
}
private int findSum(TreeNode root)
{
if (root.left == null && root.right == null)
{
int sum = root.val;
map.put(sum,map.getOrDefault(sum,0)+1);
if (map.get(sum) > max)
{
max = map.get(sum);
result = new ArrayList<Integer>();
result.add(sum);
}
else if (map.get(sum) == max)
result.add(sum);
// System.out.println(root.val+" "+result);
return sum;
}
int left = root.left != null ? findSum(root.left) : Integer.MIN_VALUE;
int right = root.right != null ? findSum(root.right) : Integer.MIN_VALUE;
int sum = root.val+(left == Integer.MIN_VALUE ? 0 : left)+(right == Integer.MIN_VALUE ? 0 : right);
map.put(sum,map.getOrDefault(sum,0)+1);
if (map.get(sum) > max)
{
max = map.get(sum);
result = new ArrayList<Integer>();
result.add(sum);
}
else if (map.get(sum) == max)
result.add(sum);
// System.out.println(root.val+" "+result);
return sum;
}
}