Skip to content

Commit dc4fa31

Browse files
another iterative version of preorder traversal
1 parent a05f3b5 commit dc4fa31

File tree

1 file changed

+17
-1
lines changed

1 file changed

+17
-1
lines changed

MEDIUM/src/medium/BinaryTreePreorderTraversal.java

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
import classes.TreeNode;
88

99
public class BinaryTreePreorderTraversal {
10-
public List<Integer> preorderTraversal_iterative(TreeNode root) {
10+
public List<Integer> preorderTraversal_iterative_original(TreeNode root) {
1111
List<Integer> list = new ArrayList();
1212
Stack<TreeNode> stack = new Stack();
1313
if(root == null) return list;
@@ -21,6 +21,22 @@ public List<Integer> preorderTraversal_iterative(TreeNode root) {
2121
return list;
2222
}
2323

24+
public List<Integer> preorderTraversal_iterative_online(TreeNode root) {
25+
List<Integer> list = new ArrayList();
26+
Stack<TreeNode> stack = new Stack();
27+
if(root == null) return list;
28+
while(root != null || !stack.isEmpty()){
29+
if(root != null){
30+
list.add(root.val);
31+
stack.push(root);
32+
root = root.left;
33+
} else {
34+
root = stack.pop().right;
35+
}
36+
}
37+
return list;
38+
}
39+
2440
//recursive solution is really trivial:
2541
public List<Integer> preorderTraversal_recursive(TreeNode root) {
2642
List<Integer> list = new ArrayList();

0 commit comments

Comments
 (0)