145. 二叉树的后序遍历

递归

class Solution {
    public List postorderTraversal(TreeNode root) {   
        List ls = new ArrayList();
        end(root, ls);
        return ls;
    }
    public static void end(TreeNode T, List ls) {
        if (T == null)
            return;
        end(T.left, ls);
        end(T.right, ls);
        ls.add(T.val);
    }
}

递推有点难

public List postorderTraversal(TreeNode root) {
        LinkedList ls = new LinkedList();
        LinkedList output = new LinkedList();
        if (root == null) {
            return output;
        }
        ls.add(root);
        while (!ls.isEmpty()) {
            TreeNode node = ls.pollLast();
            output.addFirst(node.val);
            if (node.left != null) {
                ls.add(node.left);
            }
            if (node.right != null) {
                ls.add(node.right);
            }
        }
        return output;
    }
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

public List postorderTraversal(TreeNode root) {
    List res = new ArrayList();
    if(root == null) return res;
    Stack stack = new Stack();
    TreeNode cur = root;
    TreeNode last = null;

    while(cur != null || !stack.isEmpty()){
        while(cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        if(cur.right == null || cur.right == last){
            res.add(cur.val);
            stack.pop();
            last = cur;
            cur = null;
        }else{
            cur = cur.right;
        }
    }
    return res;
}
}

public List postorderTraversal(TreeNode root) {
        List list = new ArrayList();
        Stack stk1 = new Stack();
        Stack stk2 = new Stack();
        while(root!=null || !stk1.isEmpty()){
            while(root!=null){
                stk1.push(root);
                stk2.push('n');//n=>no=>访问的非当前节点
                root = root.left;
            }
            while(!stk1.isEmpty() && stk2.peek()=='y')//y=>yes=>访问的当前节点
            {
                list.add(stk1.pop().val);
                stk2.pop();
            }
            if(!stk1.isEmpty()){
                stk2.pop();
                stk2.push('y');
                root = stk1.peek();
                root = root.right;
            }
        }
        return list;
    }