22
33import com .fishercoder .common .classes .TreeNode ;
44
5- import java .util .ArrayList ;
6- import java .util .List ;
7- import java .util .Stack ;
5+ import java .util .*;
86
9- /**Given a binary tree, return the preorder traversal of its nodes' values.
7+ /**
8+ * 144. Binary Tree Preorder Traversal
9+ * Given a binary tree, return the preorder traversal of its nodes' values.
1010
1111 For example:
1212 Given binary tree {1,#,2,3},
2020 Note: Recursive solution is trivial, could you do it iteratively?*/
2121
2222public class _144 {
23- public List <Integer >preorderTraversal_iterative_original (TreeNode root ) {
23+
24+ public List <Integer >preorderTraversal_iterative (TreeNode root ) {
2425List <Integer >list =new ArrayList ();
25- Stack <TreeNode >stack =new Stack ();
2626if (root ==null )return list ;
27+ Deque <TreeNode >stack =new ArrayDeque <>();
2728stack .push (root );
2829while (!stack .isEmpty ()){
2930TreeNode curr =stack .pop ();
3031list .add (curr .val );
32+ /**We push right nodes onto the stack first, since they'll be popped out later than
33+ * the left nodes, to meet the preorder: root -> left -> right. */
3134if (curr .right !=null )stack .push (curr .right );
3235if (curr .left !=null )stack .push (curr .left );
3336 }
3437return list ;
3538 }
3639
37- public List <Integer >preorderTraversal_recursive_1 (TreeNode root ) {
40+ public List <Integer >preorderTraversal_recursive (TreeNode root ) {
3841List <Integer >list =new ArrayList ();
3942return pre (root ,list );
4043 }
@@ -47,18 +50,4 @@ List<Integer> pre(TreeNode root, List<Integer> list){
4750return list ;
4851 }
4952
50-
51- public List <Integer >preorderTraversal_recursive_2 (TreeNode root ) {
52- List <Integer >result =new ArrayList ();
53- if (root !=null )dfs (root ,result );
54- return result ;
55- }
56-
57- private void dfs (TreeNode root ,List <Integer >result ){
58- result .add (root .val );
59- if (root .left !=null )dfs (root .left ,result );
60- if (root .right !=null )dfs (root .right ,result );
61- }
62-
63-
6453}