package tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
 * Given a binary tree, return the postorder traversal of its nodes' values.
 * For example:
 * Given binary tree {1,#,2,3},
 * <pre>
 * 1
 *  \
 *   2
 *  /
 * 3
 * </pre>
 * return [3,2,1].
 */
public class BinaryTreePostorderTraversal {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    private enum Status {
        unvisited, visiting;
    }

    private static class TreeNodeWrapper {
        private TreeNode node;
        private Status status;

        TreeNodeWrapper(TreeNode node) {
            this.node = node;
            status = Status.unvisited;
        }
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) return res;
        Stack<TreeNodeWrapper> stack = new Stack<>();
        stack.push(new TreeNodeWrapper(root));
        while (!stack.isEmpty()) {
            TreeNodeWrapper wrapper = stack.peek();
            TreeNode node = wrapper.node;
            if (wrapper.status == Status.visiting || (node.left == null && node.right == null)) {
                res.add(node.val);
                stack.pop();
            } else {
                wrapper.status = Status.visiting;
                if (node.right != null) {
                    stack.push(new TreeNodeWrapper(node.right));
                }
                if (node.left != null) {
                    stack.push(new TreeNodeWrapper(node.left));
                }
            }
        }
        return res;
    }
}

@@ -402,410 +402,8 @@
 l %7B%0A
-    private static class TreeNode %7B%0A        int val;%0A        TreeNode left;%0A        TreeNode right;%0A    %7D%0A%0A    private enum Status %7B%0A        unvisited, visiting;%0A    %7D%0A%0A    private static class TreeNodeWrapper %7B%0A        private TreeNode node;%0A        private Status status;%0A%0A        TreeNodeWrapper(TreeNode node) %7B%0A            this.node = node;%0A            status = Status.unvisited;%0A        %7D%0A    %7D%0A%0A
     
@@ -567,23 +567,16 @@
 TreeNode
-Wrapper
 %3E stack 
@@ -604,134 +604,237 @@
     
-stack.push(new TreeNodeWrapper(root));%0A        while (!stack.isEmpty()) %7B%0A            TreeNodeWrapper wrapper = stack.peek();%0A
+TreeNode current = root, prev = null;%0A        while (!stack.isEmpty() %7C%7C current != null) %7B%0A            if (current != null) %7B%0A                stack.push(current);%0A                current = current.left;%0A            %7D else %7B%0A    
     
@@ -861,20 +861,20 @@
 e = 
-wrapper.node
+stack.peek()
 ;%0A  
@@ -887,58 +887,25 @@
     
-if (wrapper.status == Status.visiting %7C%7C
+    if
  (node.
-lef
+righ
 t ==
@@ -914,10 +914,10 @@
 ull 
-&&
+%7C%7C
  nod
@@ -931,17 +931,20 @@
  == 
-null)) %7B%0A
+prev) %7B%0A    
     
@@ -994,90 +994,30 @@
     
-stack.pop();%0A            %7D else %7B%0A                wrapper.status = Status.visiting
+    prev = stack.pop()
 ;%0A  
@@ -1034,85 +1034,47 @@
     
-if (node.right != null) %7B%0A                    stack.push(new TreeNodeWrapper(
+%7D else %7B%0A                    current = 
 node
@@ -1079,18 +1079,16 @@
 de.right
-))
 ;%0A      
@@ -1115,118 +1115,82 @@
     
+%7D%0A
     
-if (node.left != null) %7B%0A         
+    %7D%0A        return res;%0A
     
-  
+%7D%0A%0A
     
- stack.push(new TreeNodeWrapper(node.left));%0A                %7D
+private static class TreeNode %7B
 %0A   
@@ -1186,37 +1186,40 @@
 eNode %7B%0A        
-    %7D
+int val;
 %0A        %7D%0A     
@@ -1203,33 +1203,46 @@
 nt val;%0A        
-%7D
+TreeNode left;
 %0A        return 
@@ -1230,32 +1230,36 @@
 ft;%0A        
+T
 re
-turn res
+eNode right
 ;%0A    %7D%0A%7D%0A

update post order traversal