|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.Collections; |
| 5 | +importjava.util.List; |
| 6 | +importjava.util.Stack; |
| 7 | + |
| 8 | +importutils.CommonUtils; |
| 9 | +importclasses.TreeNode; |
| 10 | + |
| 11 | +publicclassBinaryTreePostOrderTraversal { |
| 12 | +/**I was really confused about how iterative version works for POST-order traversal, since we'lld need to add a field in TreeNode |
| 13 | + class called "visited", to mark this node has been visited before, otherwise it goes into indefinite loop. |
| 14 | + Then I turned to Discuss, only found that the top-voted one is actually using such a trick: |
| 15 | + modify the code for pre-order traversal so that it becomes root->right->left, and then reverse the result to get left->right->root, so tricky!!!*/ |
| 16 | +publicstaticList<Integer>postorderTraversal_iterative(TreeNoderoot) { |
| 17 | +List<Integer>result =newArrayList(); |
| 18 | +Stack<TreeNode>stack =newStack(); |
| 19 | +if(root ==null)returnresult; |
| 20 | +stack.push(root); |
| 21 | +while(!stack.isEmpty()){ |
| 22 | +root =stack.pop(); |
| 23 | +result.add(root.val); |
| 24 | +if(root.left !=null)stack.push(root.left); |
| 25 | +if(root.right !=null)stack.push(root.right); |
| 26 | + } |
| 27 | +Collections.reverse(result); |
| 28 | +returnresult; |
| 29 | + } |
| 30 | + |
| 31 | +publicstaticvoidmain(String...strings){ |
| 32 | +// TreeNode root = new TreeNode(1); |
| 33 | +// root.left = new TreeNode(2); |
| 34 | +// root.right = new TreeNode(3); |
| 35 | + |
| 36 | +// TreeNode root = new TreeNode(1); |
| 37 | +// root.left = new TreeNode(2); |
| 38 | + |
| 39 | +TreeNoderoot =newTreeNode(1); |
| 40 | +root.right =newTreeNode(2); |
| 41 | +List<Integer>result =postorderTraversal_iterative(root); |
| 42 | +CommonUtils.printList(result); |
| 43 | + } |
| 44 | + |
| 45 | +publicList<Integer>postorderTraversal_recursive(TreeNoderoot) { |
| 46 | +List<Integer>result =newArrayList(); |
| 47 | +returnpost(root,result); |
| 48 | + } |
| 49 | + |
| 50 | +List<Integer>post(TreeNoderoot,List<Integer>result){ |
| 51 | +if(root ==null)returnresult; |
| 52 | +post(root.left,result); |
| 53 | +post(root.right,result); |
| 54 | +result.add(root.val); |
| 55 | +returnresult; |
| 56 | + } |
| 57 | +} |