forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
FindMode.java
101 lines (89 loc) · 2.92 KB
/
FindMode.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
/*https://leetcode.com/problems/find-mode-in-binary-search-tree/*/
class Solution {
int maxCount;
int currCount;
int currElem;
List<Integer> list;
Solution()
{
list = new ArrayList<Integer>();
maxCount = 0;
currCount = -1;
currElem = Integer.MIN_VALUE;
}
public int[] findMode(TreeNode root) {
Solution sol = new Solution();
traverseInOrder(sol,root);
//update the result in a similar way
if (sol.currCount > sol.maxCount)
{
sol.maxCount = sol.currCount;
sol.list.clear();
sol.list.add(sol.currElem);
}
else if (sol.currCount == sol.maxCount)
{
sol.list.add(sol.currElem);
}
//convert and return
int[] res = new int[sol.list.size()];
int i = 0;
for (Integer elem : sol.list)
res[i++] = elem;
return res;
}
public void traverseInOrder(Solution sol, TreeNode root) {
//if root is not null
if (root != null)
{
//recursion call for left subtree
traverseInOrder(sol,root.left);
//if it is the very first element
if (sol.currCount == -1)
{
//store it as the current element
sol.currElem = root.val;
//increase count to 1
sol.currCount = 1;
}
//if it is not the first element
else
{
//if current element is equal to current node value
if (sol.currElem == root.val)
{
//increase the count
++sol.currCount;
}
/*
if current node value is different i.e.
we cannot get the current element value anywhere else
as per the property of BST
*/
else
{
//if current count is greater than or equal to max count
if (sol.currCount >= sol.maxCount)
{
//if it is strictly greater
if (sol.currCount > sol.maxCount)
{
//update the max count
sol.maxCount = sol.currCount;
//delete all previous elements
sol.list.clear();
}
//add the element to list
sol.list.add(sol.currElem);
}
//set current count to 1 for the next element
sol.currCount = 1;
//set the current node value to current element
sol.currElem = root.val;
}
}
//recursion call for right subtree
traverseInOrder(sol,root.right);
}
}
}