package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**Given a binary tree, return the postorder traversal of its nodes' values.

 For example:
 Given binary tree {1,#,2,3},
 1
  \
   2
  /
 3
 return [3,2,1].

 Note: Recursive solution is trivial, could you do it iteratively?*/

public class _145 {
	/**A tricky one: Modify the code for pre-order traversal so that it becomes root->right->left, and then reverse the result to get left->right->root.*/
    public static List<Integer> postorderTraversal_iterative(TreeNode root) {
        List<Integer> result = new ArrayList();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            result.add(root.val);
            if (root.left != null) {
                stack.push(root.left);
            }
            if (root.right != null) {
                stack.push(root.right);
            }
        }
        Collections.reverse(result);
        return result;
    }

    public List<Integer> postorderTraversal_recursive(TreeNode root) {
        List<Integer> result = new ArrayList();
        return post(root, result);
    }

    List<Integer> post(TreeNode root, List<Integer> result) {
        if (root == null) {
            return result;
        }
        post(root.left, result);
        post(root.right, result);
        result.add(root.val);
        return result;
    }
}

@@ -187,16 +187,59 @@
 ck;%0A%0A/**
+%0A * 145. Binary Tree Postorder Traversal%0A%0A 
 Given a 
@@ -480,12 +480,57 @@
 5 %7B%0A
-%09/**
+  public static class Solution1 %7B%0A    /**%0A     * 
 A tr
@@ -578,16 +578,23 @@
 raversal
+%0A     *
  so that
@@ -623,16 +623,23 @@
 t-%3Eleft,
+%0A     *
  and the
@@ -684,16 +684,22 @@
 t-%3Eroot.
+%0A     
 */%0A    p
@@ -747,18 +747,8 @@
 rsal
-_iterative
 (Tre
@@ -759,34 +759,32 @@
 e root) %7B%0A      
- 
- 
 List%3CInteger%3E re
@@ -809,26 +809,24 @@
 st();%0A      
-  
 if (root == 
@@ -825,36 +825,32 @@
 root == null) %7B%0A
-    
         return r
@@ -858,30 +858,26 @@
 sult;%0A      
-  %7D%0A  
+%7D%0A
       Stack%3C
@@ -903,26 +903,24 @@
 ew Stack();%0A
-  
       stack.
@@ -937,18 +937,16 @@
 ;%0A      
-  
 while (!
@@ -972,20 +972,16 @@
         
-    
 root = s
@@ -996,28 +996,24 @@
 ();%0A        
- 
-   
 result.add(r
@@ -1022,36 +1022,32 @@
 t.val);%0A        
-   
- 
 if (root.left !=
@@ -1047,38 +1047,32 @@
 left != null) %7B%0A
-      
           stack.
@@ -1100,24 +1100,18 @@
     
-    %7D%0A  
+%7D%0A
         
   if
@@ -1102,26 +1102,24 @@
   %7D%0A        
-  
 if (root.rig
@@ -1128,30 +1128,24 @@
  != null) %7B%0A
-      
           st
@@ -1174,28 +1174,24 @@
         
-    
 %7D%0A      
   %7D%0A    
@@ -1178,30 +1178,26 @@
     %7D%0A      
- 
- 
 %7D%0A
-  
       Collec
@@ -1217,34 +1217,32 @@
 (result);%0A      
-  
 return result;%0A 
@@ -1242,24 +1242,62 @@
 sult;%0A    %7D%0A
+  %7D%0A%0A  public static class Solution2 %7B
 %0A    public 
@@ -1332,18 +1332,8 @@
 rsal
-_recursive
 (Tre
@@ -1342,26 +1342,24 @@
 ode root) %7B%0A
-  
       List%3CI
@@ -1388,26 +1388,24 @@
 rrayList();%0A
-  
       return
@@ -1490,26 +1490,24 @@
 %3E result) %7B%0A
-  
       if (ro
@@ -1524,28 +1524,24 @@
 ) %7B%0A        
-    
 return resul
@@ -1539,26 +1539,24 @@
 urn result;%0A
-  
       %7D%0A    
@@ -1553,26 +1553,24 @@
     %7D%0A      
-  
 post(root.le
@@ -1578,26 +1578,24 @@
 t, result);%0A
-  
       post(r
@@ -1610,26 +1610,24 @@
 t, result);%0A
-  
       result
@@ -1644,26 +1644,24 @@
 val);%0A      
-  
 return resul
@@ -1669,10 +1669,14 @@
 ;%0A    %7D%0A
+  %7D%0A
 %7D%0A

refactor 145