二叉树的后序遍历

递归写法

 public int[] postorderTraversal (TreeNode root) {
        // write code here
         List<Integer> list=new ArrayList<Integer>();
        dfs(list,root);
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }
    public void dfs(List<Integer> list,TreeNode root){
        if (root==null) return;
        dfs(list,root.left);
        dfs(list,root.right);
        list.add(root.val);
    }

非递归写法

两个栈的写法

 public int[] postorderTraversal (TreeNode root) {
        // write code here

        if(root==null) return new int[0];

        Deque<TreeNode> stack1=new LinkedList<TreeNode>();
        Deque<Integer> stack2=new LinkedList<Integer>();
        stack1.push(root);
        while (stack1.isEmpty()){
            TreeNode p=stack1.pop();
            stack2.push(p.val);
            if (p.left!=null) stack1.push(p.left);
            if(p.right!=null) stack1.push(p.right);

        }
        int l=stack2.size();
        int[] res=new int[l];
        for (int i=0;i<l;i++){
            res[i]=stack2.pop();
        }
        return res;
    }

一个栈

 public int[] postorderTraversal (TreeNode root) {
        // write code here
        if(root==null) return new int[0];

        Deque<TreeNode> stack=new LinkedList<>();
        List<Integer> list=new ArrayList<>();

        TreeNode t=root;
        TreeNode c=root;
        stack.push(t);
        while (!stack.isEmpty()){
            t=stack.peek();
            if(t.left!=null&&c!=t.left&&c!=t.right){
                stack.push(t.left);
            }else if(t.right!=null&&c!=t.right){
                stack.push(t.right);
            }else {
                list.add(t.val);
                stack.pop();
                c=t;
            }
        }

        int[] res=new int[list.size()];
        for (int i=0;i<res.length;i++){
            res[i]=list.get(i);
        }
        return res;
    }