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

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[] inorderTraversal (TreeNode root) {
                // write code here
        //方法一：递归遍历
        //特殊值处理，当树为空时，直接返回空数组
//        if(root == null){
//            return new int[0];
//        }
//        //创建一个ArrayList对象，因为书的节点个数未知
//        ArrayList<Integer> arrayList = new ArrayList<>();
//        //调用接口，实现中根遍历，遍历结果保存在ArrayList数组中
//        midRoot(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();  //弹出栈顶元素
//            //如果栈顶元素右节点不为空，压入栈中，此时需要添加!pop.isFlag()，否则会存在两次加入当前节点的右孩子节点；
//            // 对于左节点则不用考虑这种情况，因为左节点永远比父节点先出栈
//            if(pop.right != null && !pop.right.isFlag() && !pop.isFlag()){
//                pop.right.setFlag(false);
//                stack.push(pop.right);
//            }
//            if(pop.isFlag()){
//                arrayList.add(pop.val);  //遍历栈顶元素，并将栈顶元素添加到ArrayList数组
//            }else{
//                pop.setFlag(true);
//                stack.push(pop);
//            }
//            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;

        //方法三：迭代遍历
        //特殊值处理，当树为空时，直接返回空数组
        if(root == null){
            return new int[0];
        }
        //创建一个ArrayList对象，因为书的节点个数未知
        ArrayList<Integer> arrayList = new ArrayList<>();
        //创建一个栈，存储的对象是树的节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode head = stack.pop();
        while (head != null || !stack.isEmpty()){
            if(head != null){//如果当前节点不为空，说明父节点有左儿子节点；将当前节点压入栈中，遍历当前节点的左儿子节点
                stack.push(head);
                head = head.left;
            }else {//如果当前节点为空，说明父节点没有左儿子节点；从栈中弹出当前节点的父节点,并将父节点的值输出，遍历当前节点的右儿子节点
                head = stack.pop();
                arrayList.add(head.val);
                head = head.right;
            }
        }
        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;
    }
}