题解 | #二叉树的后序遍历#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        // postOrder(root,list);
        // return list.stream().mapToInt(Integer::intValue).toArray();
        return postOrder2(root,list);
    }
    //递归写法
    public void postOrder(TreeNode root,ArrayList<Integer> list){
        if(root==null) return;
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
    }
    //非递归写法 可以用两个栈来解决，先序是中左右 ，后序时左右中，那可以先找到中右左， 再入栈
    public int[] postOrder2(TreeNode root,ArrayList<Integer> list){
        if(root==null) return new int[]{};
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        TreeNode node = root;
        stack1.push(root);
        while(!stack1.isEmpty()){
            node = stack1.pop();
            list.add(node.val);
            if(node.left!=null)
               stack1.push(node.left);
            if(node.right!=null)
                stack1.push(node.right);

        }
       for(int nums:list){
        stack2.push(nums);
       }
       list = new ArrayList<Integer>();
        while(!stack2.isEmpty()){
            list.add(stack2.pop());
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}