2020-04-09(94. 二叉树的中序遍历**)

难度 中等
还是数据结构的基本操作，有递归和迭代两种方法。
方法一：递归，效率更高。
执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :37.4 MB, 在所有 Java 提交中击败了5.23%的用户

    List<Integer> mList = new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root != null){
            inorderTraversal(root.left);
            mList.add(root.val);
            inorderTraversal(root.right);
        }
        return mList;
    }

方法二：迭代。
执行用时 :1 ms, 在所有 Java 提交中击败了59.50%的用户
内存消耗 :37.6 MB, 在所有 Java 提交中击败了5.23%的用户

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> mList = new ArrayList<Integer>();
        Stack<TreeNode> mStack = new Stack<TreeNode>();
        TreeNode cur = root;
        while(cur != null || !mStack.isEmpty()){
            while(cur != null){
                mStack.push(cur);
                cur = cur.left;
            }
            cur = mStack.pop();
            mList.add(cur.val);
            cur = cur.right;
        }
        return mList;
    }