• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# 145. Binary Tree Postorder Traversal|Time: O(n)|Space:O(n)

a guest Aug 21st, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import java.util.List;
2. import java.util.ArrayList;
3. import java.util.Stack;
4.
5. // Problem: https://leetcode.com/problems/binary-tree-inorder-traversal/
7. // Solution adapted from: https://www.programcreek.com/2012/12/leetcode-solution-of-binary-tree-inorder-traversal-in-java/
8.
9. public class PostorderIterative {
10.
11.     public static class TreeNode {
12.         int val;
13.         TreeNode left;
14.         TreeNode right;
15.         TreeNode(int x) { val = x; }
16.     }
17.
18.     public static List<Integer> postorderIterativeTraversal(TreeNode root) {
19.         List<Integer> result = new ArrayList<>();
20.         Stack<TreeNode> stack1 = new Stack<>();
21.         Stack<TreeNode> stack2 = new Stack<>();
22.
23.         if (root == null) {
24.             return result;
25.         }
26.
28.
29.         while(!stack1.isEmpty()) {
30.             TreeNode node = stack1.pop();
31.             stack2.push(node);
32.             if(node.left != null) {
33.                 stack1.push(node.left);
34.             }
35.
36.             if(node.right != null) {
37.                 stack1.push(node.right);
38.             }
39.         }
40.
41.         while(!stack2.isEmpty()) {
42.             TreeNode node = stack2.pop();
44.         }
45.
46.         return result;
47.     }
48.
49.     public static void main(String args[]){
50.
51.         TreeNode root = new TreeNode(10);
52.         root.left = new TreeNode(8);
53.         root.right = new TreeNode(2);
54.         root.left.left = new TreeNode(3);
55.         root.left.right = new TreeNode(5);
56.         root.right.left = new TreeNode(7);
57.
58.         List<Integer> result = postorderIterativeTraversal(root);
59.         System.out.println(result.toString());
60.         // Expected output: 3 5 8 7 2 10
61.     }
62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?