Repository navigation
Expand file tree
/
Copy pathMainClass.java
More file actions
111 lines (91 loc) · 2.87 KB
/
Copy pathMainClass.java
File metadata and controls
111 lines (91 loc) · 2.87 KB
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
108
109
110
111
package binarySearch1;
import java.util.*;
public class MainClass {
// 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;
}
}
public List<Integer> rightSideView(TreeNode root) {
ArrayList<Integer> ans = new ArrayList<>();
int level = 0;
rightSideView(root, level, ans);
return ans;
}
void rightSideView(TreeNode root, int level, ArrayList<Integer> ans) {
if(root == null) return;
if(ans.size() == level) {
ans.add(root.val);
}
rightSideView(root.right, level+1, ans);
rightSideView(root.left, level+1, ans);
}
static ArrayList <Integer> verticalOrder(Node root) {
Map<Integer, ArrayList<Integer>> map = new TreeMap<>();
if(root == null) return null;
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(0, root));
while(!q.isEmpty()) {
Pair cur = q.poll();
int key = cur.hd;
if(!map.containsKey(key)) {
map.put(key, new ArrayList<Integer>());
}
map.get(key).add(cur.node.data);
if(cur.node.left != null) {
q.add(new Pair(key-1, cur.node.left));
}
if(cur.node.right != null) {
q.add(new Pair(key+1, cur.node.right));
}
}
ArrayList<Integer> ans = new ArrayList<>();
for(ArrayList<Integer> e: map.values()) {
ans.addAll(e);
}
return ans;
}
static class Pair {
int hd;
Node node;
public Pair(int hd, Node node) {
this.hd = hd;
this.node = node;
}
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if(root == null) return ans;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
q.offer(null);
ArrayList<Integer> curList = new ArrayList<>();
while(!q.isEmpty()) {
TreeNode cur = q.poll();
if(cur == null) {
ans.add(curList);
if(q.isEmpty()) return ans;
q.offer(null);
curList = new ArrayList<>();
} else {
curList.add(cur.val);
if(cur.left != null) {
q.add(cur.left);
}
if(cur.right != null) {
q.add(cur.right);
}
}
}
return ans;
}
}