forked from striver79/FreeKaTreeSeries
-
Notifications
You must be signed in to change notification settings - Fork 0
/
L23_bottomViewOfBtJava
33 lines (30 loc) · 949 Bytes
/
L23_bottomViewOfBtJava
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
class Solution
{
//Function to return a list containing the bottom view of the given tree.
public ArrayList <Integer> bottomView(Node root)
{
ArrayList<Integer> ans = new ArrayList<>();
if(root == null) return ans;
Map<Integer, Integer> map = new TreeMap<>();
Queue<Node> q = new LinkedList<Node>();
root.hd = 0;
q.add(root);
while(!q.isEmpty()) {
Node temp = q.remove();
int hd = temp.hd;
map.put(hd, temp.data);
if(temp.left != null) {
temp.left.hd = hd - 1;
q.add(temp.left);
}
if(temp.right != null) {
temp.right.hd = hd + 1;
q.add(temp.right);
}
}
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
ans.add(entry.getValue());
}
return ans;
}
}