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) {
        if(root==null){
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> s = new Stack<TreeNode>();
//当树都访问完，并且栈为空再跳出循环
        while(root!=null || !s.empty()){
            //访问到最左边结点
            while(root!=null){
                s.push(root);
                root=root.left;
            }
            TreeNode node = s.pop();
            list.add(node.val);
            //右子树
            root = node.right;
            
        }
        int[] res = new int[list.size()];
        for(int i=0;i<list.size();++i){
            res[i] = list.get(i);
        }
        return res;

    }
}

方法一：递归

参考前序遍历可以很容易做出。

方法二：栈

与前序遍历不同，中序遍历是先访问左子树再访问根然后是右子树，所以入栈的规则就发生变化。先让所以左孩子入栈，然后访问最左结点，再遍历该节点的右子树，重复上述过程即可实现中序遍历。