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

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
        List<Integer> list = new ArrayList<>();
        postOrder3(root, list);
        int[] array = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            array[i] = list.get(i);
        }
        return array;
    }
    public void postOrder3(TreeNode root, List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;

        while(true){
            while(root != null && root != pre){
                stack.push(root);
                root = root.left;
            }
            if(!stack.empty())
                root = stack.pop();
            else{
                break;
            }
            if(root.right != null && pre != root.right){
                stack.push(root);
                root = root.right;
            }else {
                list.add(root.val);
                pre = root;
            }
        }
    }
    public void postOrder2(TreeNode root, List<Integer> list) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        TreeNode pre = null;
        if (root == null)
            return;
        stack1.push(root);

        while (!stack1.empty()) {
            root = stack1.pop();
            stack2.push(root);
            if(root.left != null){
                stack1.push(root.left);
            }
            if(root.right != null){
                stack1.push(root.right);
            }
        }
        while(!stack2.empty()){
            list.add(stack2.pop().val);
        }
    }
    public void postOrder(TreeNode root, List<Integer> list) {
        if (root == null)
            return;
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(root.val);
    }
}