|
8 | 8 | importjava.util.List; |
9 | 9 | importjava.util.Stack; |
10 | 10 |
|
11 | | -/** |
12 | | - * 144. Binary Tree Preorder Traversal |
13 | | -
|
14 | | - Given a binary tree, return the preorder traversal of its nodes' values. |
15 | | -
|
16 | | - For example: |
17 | | - Given binary tree {1,#,2,3}, |
18 | | - 1 |
19 | | - \ |
20 | | - 2 |
21 | | - / |
22 | | - 3 |
23 | | - return [1,2,3]. |
24 | | -
|
25 | | - Note: Recursive solution is trivial, could you do it iteratively?*/ |
26 | | - |
27 | 11 | publicclass_144 { |
28 | | -publicstaticclassSolution1 { |
29 | | -publicList<Integer>preorderTraversal(TreeNoderoot) { |
30 | | -List<Integer>list =newArrayList<>(); |
31 | | -Stack<TreeNode>stack =newStack<>(); |
32 | | -stack.push(root); |
33 | | -while (!stack.isEmpty()) { |
34 | | -TreeNodecurr =stack.pop(); |
35 | | -if (curr !=null) { |
36 | | -list.add(curr.val); |
37 | | -stack.push(curr.right); |
38 | | -stack.push(curr.left); |
| 12 | +publicstaticclassSolution1 { |
| 13 | +publicList<Integer>preorderTraversal(TreeNoderoot) { |
| 14 | +List<Integer>list =newArrayList<>(); |
| 15 | +Stack<TreeNode>stack =newStack<>(); |
| 16 | +stack.push(root); |
| 17 | +while (!stack.isEmpty()) { |
| 18 | +TreeNodecurr =stack.pop(); |
| 19 | +if (curr !=null) { |
| 20 | +list.add(curr.val); |
| 21 | +stack.push(curr.right); |
| 22 | +stack.push(curr.left); |
| 23 | + } |
| 24 | + } |
| 25 | +returnlist; |
39 | 26 | } |
40 | | - } |
41 | | -returnlist; |
42 | 27 | } |
43 | | - } |
44 | 28 |
|
45 | | -publicstaticclassSolution2 { |
46 | | -publicList<Integer>preorderTraversal(TreeNoderoot) { |
47 | | -List<Integer>list =newArrayList(); |
48 | | -returnpre(root,list); |
49 | | - } |
| 29 | +publicstaticclassSolution2 { |
| 30 | +publicList<Integer>preorderTraversal(TreeNoderoot) { |
| 31 | +List<Integer>list =newArrayList(); |
| 32 | +returnpre(root,list); |
| 33 | +} |
50 | 34 |
|
51 | | -List<Integer>pre(TreeNoderoot,List<Integer>list) { |
52 | | -if (root ==null) { |
53 | | -returnlist; |
54 | | - } |
55 | | -list.add(root.val); |
56 | | -pre(root.left,list); |
57 | | -pre(root.right,list); |
58 | | -returnlist; |
| 35 | +List<Integer>pre(TreeNoderoot,List<Integer>list) { |
| 36 | +if (root ==null) { |
| 37 | +returnlist; |
| 38 | + } |
| 39 | +list.add(root.val); |
| 40 | +pre(root.left,list); |
| 41 | +pre(root.right,list); |
| 42 | +returnlist; |
| 43 | + } |
59 | 44 | } |
60 | | - } |
61 | 45 |
|
62 | | -publicstaticclassSolution3 { |
63 | | -publicList<Integer>preorderTraversal(TreeNoderoot) { |
64 | | -List<Integer>list =newArrayList<>(); |
65 | | -Stack<TreeNode>stack =newStack<>(); |
66 | | -while (!stack.isEmpty() ||root !=null) { |
67 | | -while (root !=null) { |
68 | | -list.add(root.val); |
69 | | -stack.push(root); |
70 | | -root =root.left; |
| 46 | +publicstaticclassSolution3 { |
| 47 | +publicList<Integer>preorderTraversal(TreeNoderoot) { |
| 48 | +List<Integer>list =newArrayList<>(); |
| 49 | +Stack<TreeNode>stack =newStack<>(); |
| 50 | +while (!stack.isEmpty() ||root !=null) { |
| 51 | +while (root !=null) { |
| 52 | +list.add(root.val); |
| 53 | +stack.push(root); |
| 54 | +root =root.left; |
| 55 | + } |
| 56 | +root =stack.pop(); |
| 57 | +root =root.right; |
| 58 | + } |
| 59 | +returnlist; |
71 | 60 | } |
72 | | -root =stack.pop(); |
73 | | -root =root.right; |
74 | | - } |
75 | | -returnlist; |
76 | 61 | } |
77 | | - } |
78 | 62 | } |