forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary Tree Preorder Traversal.java
More file actions
executable file
·140 lines (119 loc) · 3.34 KB
/
Binary Tree Preorder Traversal.java
File metadata and controls
executable file
·140 lines (119 loc) · 3.34 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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
E
1522009726
tags: Stack, Tree, DFS, BFS
#### Recursive
- 加root, left, then right. Obvious
- Divide and conquer
- 其实也不需要helper function
#### Iterative
- 先加root, 然后push上需要末尾process的在stack垫底(root.right), 然后push root.left
- Stack: push curr, push right, push left.
```
/*
Given a binary tree, return the preorder traversal of its nodes' values.
Note
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Example
Challenge
Can you do it without recursion?
Tags Expand
Tree Binary Tree
//Recommend way: using a stack
//Recursive way can be seen here: http://www.ninechapter.com/solutions/binary-tree-preorder-traversal/
*/
/*
Thoughts:
DFS, add root, then left, then right
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<>();
if (root == null) {
return rst;
}
rst.add(root.val);
rst.addAll(preorderTraversal(root.left));
rst.addAll(preorderTraversal(root.right));
return rst;
}
}
/*
Thoughts:
BFS. Want the sequence in root, left, and right.
Queue? NO. After root.left is process, it should go to root.left.left. rather than root.right.
We need to proces root, then put root.right at bottom, stack root.left on top, then work on root.left's children first.
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<>();
if (root == null) {
return rst;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
rst.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return rst;
}
}
/*
Previous notes
Recap: 12.08.2015
Draw a few nodes and will realize to use stack
Cannot use queue, because whatever added on it first, will first process.
That means if we add curr,left,right; they will be processed first... but we want to traverse all left nodes first.
IN FACT: binary tree traversal are all using stack...
*/
//Iterative
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
rst.add(node.val);
stack.push(node.right);
stack.push(node.left);
}
}
return rst;
}
}
//recursive
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
helper(rst, root);
return rst;
}
public void helper(ArrayList<Integer>rst, TreeNode node){
if (node != null) {
rst.add(node.val);
helper(rst, node.left);
helper(rst, node.right);
}
}
}
```