Advertisement
Guest User

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

a guest
Aug 21st, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.79 KB | None | 0 0
  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/
  6. // Solution adapted from: https://www.youtube.com/watch?v=nzmtCFNae9k
  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.  
  27.         stack1.add(root);
  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();
  43.             result.add(node.val);
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement