leetcode 145 二叉树的后序遍历

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

递归：

import java.util.ArrayList;
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> ret=new ArrayList<Integer>();
        if(root!=null){
            ret.addAll(postorderTraversal(root.left));
            ret.addAll(postorderTraversal(root.right));
            ret.add(root.val);
        }
        return ret;
    }
}

迭代：

import java.util.ArrayList;
import java.util.Stack;
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> ret=new ArrayList<Integer>();
        if(root==null) return ret;
        Stack<TreeNode> s=new Stack<TreeNode>();
        Stack<TreeNode> temp=new Stack<TreeNode>();
        while(root!=null||!s.isEmpty()){
            while(root!=null){
                temp.push(root);
                s.push(root);
                root=root.right;
            }
            if(!s.isEmpty()){
                root=s.pop();
                root=root.left;
            }
        }
        while(!temp.isEmpty()){
            ret.add(temp.pop().val);
        }
        return ret;
    }
}