FilesExpand file tree

 master

/

BinaryTreePreorderTraversal.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

47 lines (43 loc) · 874 Bytes

 master

/

BinaryTreePreorderTraversal.java

Top

File metadata and controls

• Code
• Blame

47 lines (43 loc) · 874 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import java.util.ArrayList;

import java.util.Stack;

/**

* Given a binary tree, return the preorder traversal of its nodes' values.

*

* For example:

* Given binary tree {1,#,2,3},

* 1

* \

* 2

* /

* 3

* return [1,2,3].

*

* Note: Recursive solution is trivial, could you do it iteratively?

*

*/

public class BinaryTreePreorderTraversal {

public ArrayList<Integer> preorderTraversal(TreeNode root) {

ArrayList<Integer> ret = new ArrayList<Integer>();

if (root == null)

return ret;

Stack<TreeNode> st = new Stack<TreeNode>();

TreeNode p = root.left;

ret.add(root.val);

st.add(root);

while (!st.isEmpty()) {

while (p != null) {

ret.add(p.val);

st.add(p);

p = p.left;

}

TreeNode node = st.pop();

p = node.right;

if (p != null) {

ret.add(p.val);

st.add(p);

p = p.left;

}

}

return ret;

}

}