/
Solution.java
executable file
·97 lines (80 loc) · 2.59 KB
/
Solution.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
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
if(root == null) return res;
stack.push(root);
while(!stack.isEmpty()){
TreeNode tmp = stack.pop();
while(tmp != null){
res.add(tmp.val);
if(tmp.right != null) stack.push(tmp.right);
if(tmp.left != null) tmp = tmp.left;
else break;
}
}
return res;
}
}
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
static enum ReturnAddress {
PRE, IN, POST, DONE;
}
static class StackState {
ReturnAddress returnAddress = ReturnAddress.PRE;
TreeNode param;
StackState(TreeNode param){
this.param = param;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> rt = new ArrayList<>();
Deque<StackState> stack = new LinkedList<>();
if(root != null)
stack.push(new StackState(root));
while(!stack.isEmpty()){
StackState current = stack.pop();
switch(current.returnAddress){
case PRE:
current.returnAddress = ReturnAddress.IN;
rt.add(current.param.val);
case IN:
current.returnAddress = ReturnAddress.POST;
if(current.param.left != null){
stack.push(current);
stack.push(new StackState(current.param.left));
continue;
}
case POST:
current.returnAddress = ReturnAddress.DONE;
if(current.param.right != null){
stack.push(current);
stack.push(new StackState(current.param.right));
continue;
}
default:
break;
}
}
return rt;
}
}