-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-545-Boundary-of-Binary-Tree.java
80 lines (71 loc) · 2.31 KB
/
LeetCode-545-Boundary-of-Binary-Tree.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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/*
https://leetcode.com/problems/boundary-of-binary-tree/discuss/101280/Java(12ms)-left-boundary-left-leaves-right-leaves-right-boundary
This solution is better than the official one.
Complexity:
O(n) leftBoundary(root.left);
O(n) leaves(root.left);
O(n) leaves(root.right);
O(n) rightBoundary(root.right);
Total: O(n)
*/
class Solution {
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
res.add(root.val);
getLeftBoundary(root.left, res);
getLeaf(root.left, res);
getLeaf(root.right, res);
getRightBoundary(root.right, res);
return res;
}
// The path from root to left most leaf (exclude)
private void getLeftBoundary(TreeNode curr, List<Integer> res) {
if (curr == null) return;
if (curr.left == null && curr.right == null) return;
res.add(curr.val);
if (curr.left != null) {
getLeftBoundary(curr.left, res);
}
else if (curr.right != null) {
getLeftBoundary(curr.right, res);
}
}
// The Path from root to right most leaf (exclude)
private void getRightBoundary(TreeNode curr, List<Integer> res) {
if (curr == null) return;
if (curr.right == null && curr.left == null) return;
if (curr.right != null) {
getRightBoundary(curr.right, res);
} else if (curr.left != null) {
getRightBoundary(curr.left, res);
}
res.add(curr.val);
}
private void getLeaf(TreeNode root, List<Integer> res) {
TreeNode curr = root;
Stack<TreeNode> stack = new Stack<>();
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
curr = stack.pop();
if (curr.left == null && curr.right == null) {
// find a leaf
res.add(curr.val);
}
curr = curr.right;
}
}
}
}