LeetCode(145)-二叉树后序遍历（递归、非递归）

import java.util.ArrayList;
import java.util.Stack;

public class l145_tree_postorder {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){
            val=x;
        }
    }
    //递归
    /*
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res=new ArrayList<>();
        if(root==null)
            return res;
        res.addAll(postorderTraversal(root.left));
        res.addAll(postorderTraversal(root.right));
        res.add(root.val);
        return res;

    }
    */
    //非递归

 public ArrayList<Integer> postorderTraversal(TreeNode root){
        ArrayList<Integer> res=new ArrayList<>();
        if(root==null)
            return res;
        Stack<TreeNode> s=new Stack<>();
        s.push(root);
        while (!s.empty()){
            TreeNode temp=s.pop();
            res.add(0,temp.val);//根右左-左右根（每次都在第一个位置添加，相当于reverse）
            //借助栈的先进后出(根左右-根右左)
            if(temp.left!=null){
                s.push(temp.left);
            }
            if(temp.right!=null){
                s.push(temp.right);
            }

        }

        return res;

    }
}