|
8 | 8 | importjava.util.List; |
9 | 9 | importjava.util.Stack; |
10 | 10 |
|
11 | | -/** |
12 | | - * 145. Binary Tree Postorder Traversal |
13 | | -
|
14 | | - Given a binary tree, return the postorder 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 [3,2,1]. |
24 | | -
|
25 | | - Note: Recursive solution is trivial, could you do it iteratively?*/ |
26 | | - |
27 | 11 | publicclass_145 { |
28 | | -publicstaticclassSolution1 { |
29 | | -/** |
30 | | - * A tricky one: Modify the code for pre-order traversal |
31 | | - * so that it becomes root->right->left, |
32 | | - * and then reverse the result to get left->right->root. |
33 | | - */ |
34 | | -publicList<Integer>postorderTraversal(TreeNoderoot) { |
35 | | -List<Integer>result =newArrayList(); |
36 | | -if (root ==null) { |
37 | | -returnresult; |
38 | | - } |
39 | | -Stack<TreeNode>stack =newStack(); |
40 | | -stack.push(root); |
41 | | -while (!stack.isEmpty()) { |
42 | | -root =stack.pop(); |
43 | | -result.add(root.val); |
44 | | -if (root.left !=null) { |
45 | | -stack.push(root.left); |
46 | | - } |
47 | | -if (root.right !=null) { |
48 | | -stack.push(root.right); |
| 12 | +publicstaticclassSolution1 { |
| 13 | +/** |
| 14 | + * A tricky/hacky one: Modify the code for pre-order traversal |
| 15 | + * so that it becomes root->right->left, |
| 16 | + * and then reverse the result to get left->right->root. |
| 17 | + */ |
| 18 | +publicList<Integer>postorderTraversal(TreeNoderoot) { |
| 19 | +List<Integer>result =newArrayList(); |
| 20 | +if (root ==null) { |
| 21 | +returnresult; |
| 22 | + } |
| 23 | +Stack<TreeNode>stack =newStack(); |
| 24 | +stack.push(root); |
| 25 | +while (!stack.isEmpty()) { |
| 26 | +root =stack.pop(); |
| 27 | +result.add(root.val); |
| 28 | +if (root.left !=null) { |
| 29 | +stack.push(root.left); |
| 30 | + } |
| 31 | +if (root.right !=null) { |
| 32 | +stack.push(root.right); |
| 33 | + } |
| 34 | + } |
| 35 | +Collections.reverse(result); |
| 36 | +returnresult; |
49 | 37 | } |
50 | | - } |
51 | | -Collections.reverse(result); |
52 | | -returnresult; |
53 | 38 | } |
54 | | - } |
55 | 39 |
|
56 | | -publicstaticclassSolution2 { |
57 | | -/**Or use a LinkedList and add values to the head, then no reverse is needed. |
58 | | - * the linked list contents get added like this: |
59 | | - * |
60 | | - * root |
61 | | - * right, root |
62 | | - * left, right, root |
63 | | - * */ |
64 | | -publicList<Integer>postorderTraversal(TreeNoderoot) { |
65 | | -List<Integer>list =newLinkedList<>(); |
66 | | -if (root ==null) { |
67 | | -returnlist; |
68 | | - } |
69 | | -Stack<TreeNode>stack =newStack<>(); |
70 | | -stack.push(root); |
71 | | -while (!stack.isEmpty()) { |
72 | | -TreeNodecurr =stack.pop(); |
73 | | -list.add(0,curr.val); |
74 | | -if (curr.left !=null) { |
75 | | -stack.push(curr.left); |
| 40 | +publicstaticclassSolution2 { |
| 41 | +/** |
| 42 | + * Or use a LinkedList and add values to the head, then no reverse is needed. |
| 43 | + * the linked list contents get added like this: |
| 44 | + * <p> |
| 45 | + * root |
| 46 | + * right, root |
| 47 | + * left, right, root |
| 48 | + */ |
| 49 | +publicList<Integer>postorderTraversal(TreeNoderoot) { |
| 50 | +List<Integer>list =newLinkedList<>(); |
| 51 | +if (root ==null) { |
| 52 | +returnlist; |
| 53 | + } |
| 54 | +Stack<TreeNode>stack =newStack<>(); |
| 55 | +stack.push(root); |
| 56 | +while (!stack.isEmpty()) { |
| 57 | +TreeNodecurr =stack.pop(); |
| 58 | +list.add(0,curr.val); |
| 59 | +if (curr.left !=null) { |
| 60 | +stack.push(curr.left); |
| 61 | + } |
| 62 | +if (curr.right !=null) { |
| 63 | +stack.push(curr.right); |
| 64 | + } |
| 65 | + } |
| 66 | +returnlist; |
76 | 67 | } |
77 | | -if (curr.right !=null) { |
78 | | -stack.push(curr.right); |
79 | | - } |
80 | | - } |
81 | | -returnlist; |
82 | 68 | } |
83 | | - } |
84 | 69 |
|
85 | | -publicstaticclassSolution3 { |
86 | | -publicList<Integer>postorderTraversal(TreeNoderoot) { |
87 | | -List<Integer>result =newArrayList(); |
88 | | -returnpost(root,result); |
89 | | - } |
| 70 | +publicstaticclassSolution3 { |
| 71 | +/** |
| 72 | + * recursive solution is trivial. |
| 73 | + */ |
| 74 | +publicList<Integer>postorderTraversal(TreeNoderoot) { |
| 75 | +List<Integer>result =newArrayList(); |
| 76 | +returnpost(root,result); |
| 77 | + } |
90 | 78 |
|
91 | | -List<Integer>post(TreeNoderoot,List<Integer>result) { |
92 | | -if (root ==null) { |
93 | | -returnresult; |
94 | | - } |
95 | | -post(root.left,result); |
96 | | -post(root.right,result); |
97 | | -result.add(root.val); |
98 | | -returnresult; |
| 79 | +List<Integer>post(TreeNoderoot,List<Integer>result) { |
| 80 | +if (root ==null) { |
| 81 | +returnresult; |
| 82 | + } |
| 83 | +post(root.left,result); |
| 84 | +post(root.right,result); |
| 85 | +result.add(root.val); |
| 86 | +returnresult; |
| 87 | + } |
99 | 88 | } |
100 | | - } |
101 | 89 | } |