[Leetcode] Binary Tree Postorder Traversal

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?

递归写法比较容易写，Morris遍历比较费劲，需要从右子树的最后一个节点来逆序的往回加。至此，树的先序，中序和后序遍历的递归写法和iterative写法已经全部搞定。

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        postorder(root, list);
        return list;
    }
    public void postorder(TreeNode root, List<Integer> list) {
        if(root == null) return;
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);
    }

    List<Integer> list;
    public List<Integer> postorderTraversal(TreeNode root) {
        list = new ArrayList<Integer>();
        TreeNode dummy = new TreeNode(0); dummy.left = root;
        TreeNode cur = dummy, temp;
        while(cur != null) {
            if(cur.left == null) cur = cur.right;
            else {
                temp = cur.left;
                while(temp.right != null && temp.right != cur) temp = temp.right;
                if(temp.right == null) {
                    temp.right = cur;
                    cur = cur.left;
                }
                else {
                    addreverse(temp, cur.left);
                    temp.right = null;
                    cur = cur.right;
                }
            }
        }
        
        return list;
    }
    private void addreverse(TreeNode from, TreeNode to) {
        if(from == to) {
            list.add(from.val);
            return; // only one TreeNode, reverse need at least two TreeNode
        }
        reverse(to, from);
        TreeNode temp = from;
        while(temp != to) {
            list.add(temp.val);
            temp = temp.right;
        }
        list.add(to.val);
        reverse(from, to);
    }
    private void reverse(TreeNode from, TreeNode to) {
        TreeNode x = from, y = from.right, z;
        x.right = null;
        while(y != to) {
            z = y.right;
            y.right = x;
            x = y;
            y = z;
        }
        y.right = x;
    }