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

import java.util.*;

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

class TreeNode {
    int val = 0;
    private boolean flag = false;   //再原来的树节点类中添加一个布尔变量，标记节点是否已经被遍历过
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val,boolean flag) {
        this.val = val;
        this.flag = flag;
    }

    public void setFlag(boolean flag) {
        this.flag = flag;
    }

    public boolean isFlag() {
        return flag;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        //方法一：递归遍历
        //特殊值处理，当树为空时，直接返回空数组
//         if(root == null){
//             return new int[0];
//         }
//         //创建一个ArrayList对象，因为书的节点个数未知
//         ArrayList<Integer> arrayList = new ArrayList<>();
//         //调用接口，实现后根遍历，遍历结果保存在ArrayList数组中
//         nextRoot(root,arrayList);
//         final Object[] obj = arrayList.toArray();  //将ArrayList数组转换为Object数组
//         int length = obj.length;  //获取Object数组的长度
//         int[] arr = new int[length];  //新创建一个长度为Object数组的长度的整型数组
//         for(int i=0;i<length;i++){
//             arr[i] = (int) obj[i];  //遍历数组，将Object对象转换为整型数
//         }
//         return arr;
        
        //方法二：迭代遍历
        //特殊值处理，当树为空时，直接返回空数组
        if(root == null){
            return new int[0];
        }
        //创建一个ArrayList对象，因为书的节点个数未知
        ArrayList<Integer> arrayList = new ArrayList<>();
        //创建一个栈，存储的对象是树的节点
        Stack<TreeNode> stack = new Stack<>();
        root.setFlag(false);
        stack.push(root);  //将根节点压入栈
        while (!stack.isEmpty()){  //当栈不为空时，退出循环
            final TreeNode pop = stack.pop();  //弹出栈顶元素
            if(pop.isFlag()){   //如果栈顶元素之前已经遍历了，则不用再压入栈，将栈顶元素添加到ArrayList数组
                arrayList.add(pop.val);  //遍历栈顶元素，并将栈顶元素添加到ArrayList数组
            }else{
                pop.setFlag(true);
                stack.push(pop);
            }
            if(pop.right != null && !pop.right.isFlag()){  //如果栈顶元素右节点不为空，压入栈中
                pop.right.setFlag(false);
                stack.push(pop.right);
            }
            if(pop.left != null && !pop.left.isFlag()){  //如果栈顶元素左节点不为空，压入栈中
                pop.left.setFlag(false);
                stack.push(pop.left);
            }
            
        }
        final Object[] obj = arrayList.toArray();  //将ArrayList对象转换为Object数组
        int length = obj.length;  //获取Object数组的长度
        int[] arr = new int[length];  //新创建一个长度为Object数组的长度的整型数组
        for(int i=0;i<length;i++){
            arr[i] = (int) obj[i];  //遍历数组，将Object对象转换为整型数
        }
        return arr;
    }
    
    /**
     * 题目描述：后根遍历，
     * @param root  树的根节点
     * @param arrayList 数组，保存树节点的值
     */
    public static void nextRoot(TreeNode root,ArrayList<Integer> arrayList){
        if(root == null){//如果根节点为空，则直接返回
            return ;
        }
        nextRoot(root.left,arrayList);  //首先遍历左子树
        nextRoot(root.right,arrayList);  //然后遍历右子树
        arrayList.add(root.val); //最后遍历根节点
    }
}