145. 二叉树的后序遍历

问题
给定一个二叉树，返回它的 后序 遍历。
例子

思路

• 递归 左结点遍历->右结点遍历->添加val
• 迭代 装Object的Stack 压栈顺序：new Integer(val)->右结点->左结点
  代码

//递归
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postOrder(root,list);
        return list;
        
    }
    public void postOrder(TreeNode root, List<Integer> list) {
        if (root==null) return ;
        if (root.left!=null) postOrder(root.left, list);
        if (root.right!=null) postOrder(root.right, list);
        list.add(root.val);
    }
}
//迭代
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null) return new ArrayList();
        
        List<Integer> list = new ArrayList<>();
        Stack stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            if (stack.peek() instanceof TreeNode) {
                TreeNode node = (TreeNode)stack.pop();
                
                stack.push(new Integer(node.val));
                if (node.right!=null) stack.push(node.right);
                if (node.left!=null) stack.push(node.left);
            } else {
                list.add((Integer)stack.pop());
            }
        }
        return list;
        
    }
}