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

/*
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) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        stack.add(root);//压入根节点
        TreeNode head = stack.pop();//弹出根节点
        while(head != null || !stack.isEmpty()){
            //如果当前节点不为空，说明父节点有左儿子节点；
            //将当前节点压入栈中，遍历当前节点的左儿子节点。
            if(head != null){
                stack.add(head);//将当前节点压入栈中
                head = head.left;//遍历当前节点的左儿子节点
            }else{
                //如果当前节点为空，说明父节点没有左儿子节点；从栈中弹出当前节点的父节点,
                //并将父节点的值输出，遍历当前节点的右儿子节点。
                head = stack.pop();//从栈中弹出当前节点的父节点
                list.add(head.val);//输出父节点的值
                head = head.right;//遍历当前节点的右儿子节点
            }
        }

        Object[] obj = list.toArray();
        int len = obj.length;
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i] = (int)obj[i];
        }

        return arr;
    }
}