-
Notifications
You must be signed in to change notification settings - Fork 1
/
Boundary_545.java
109 lines (92 loc) · 3.22 KB
/
Boundary_545.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
108
109
import java.util.*;
public class Boundary_545 {
// Standard solution #2: Preorder Traversal
// Flag=0: Root Node.
// Flag=1: Left Boundary Node.
// Flag=2: Right Boundary Node.
// Flag=3: Others(Middle Node).
public List < Integer > boundaryOfBinaryTree(TreeNode root) {
List < Integer > left_boundary = new LinkedList < > (), right_boundary = new LinkedList < > (), leaves = new LinkedList < > ();
preorder(root, left_boundary, right_boundary, leaves, 0);
left_boundary.addAll(leaves);
left_boundary.addAll(right_boundary);
return left_boundary;
}
public boolean isLeaf(TreeNode cur) {
return (cur.left == null && cur.right == null);
}
public boolean isRightBoundary(int flag) {
return (flag == 2);
}
public boolean isLeftBoundary(int flag) {
return (flag == 1);
}
public boolean isRoot(int flag) {
return (flag == 0);
}
public int leftChildFlag(TreeNode cur, int flag) {
if (isLeftBoundary(flag) || isRoot(flag))
return 1;
else if (isRightBoundary(flag) && cur.right == null)
return 2;
else return 3;
}
public int rightChildFlag(TreeNode cur, int flag) {
if (isRightBoundary(flag) || isRoot(flag))
return 2;
else if (isLeftBoundary(flag) && cur.left == null)
return 1;
else return 3;
}
public void preorder(TreeNode cur, List < Integer > left_boundary, List < Integer > right_boundary, List < Integer > leaves, int flag) {
if (cur == null)
return;
if (isRightBoundary(flag))
right_boundary.add(0, cur.val);
else if (isLeftBoundary(flag) || isRoot(flag))
left_boundary.add(cur.val);
else if (isLeaf(cur))
leaves.add(cur.val);
preorder(cur.left, left_boundary, right_boundary, leaves, leftChildFlag(cur, flag));
preorder(cur.right, left_boundary, right_boundary, leaves, rightChildFlag(cur, flag));
}
// Standard solution #1
/*
public boolean isLeaf(TreeNode t) {
return t.left == null && t.right == null;
}
public void addLeaves(List<Integer> res, TreeNode root) {
if (isLeaf(root)) {
res.add(root.val);
} else {
if (root.left != null) addLeaves(res, root.left);
if (root.right != null) addLeaves(res, root.right);
}
}
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if (root == null) return res;
// Add root
if (!isLeaf(root)) res.add(root.val);
// Add left boundary
TreeNode t = root.left;
while (t != null) {
if (!isLeaf(t)) res.add(t.val);
if (t.left != null) t = t.left;
else t = t.right;
}
// Add leaves
addLeaves(res, root);
// Add right boundary
Stack<Integer> s = new Stack<>();
t = root.right;
while (t != null) {
if (!isLeaf(t)) s.push(t.val);
if (t.right != null) t = t.right;
else t = t.left;
}
while (!s.empty()) res.add(s.pop());
return res;
}
*/
}