1.问题

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

2.解题思路

2.1 递归

类似二叉树的前序遍历，中序遍历规则为 左-根-右，只要对前序遍历-递归稍作调整，即可实现；

复杂度分析

• 时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

• 空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

2.2 迭代（栈）

若利用栈（迭代思想），则需要调整下入栈顺序，遍历顺序
1）先遍历根节点，入栈

2）循环遍历左子树


3）到达最左边，出栈，遍历该节点右子树，入栈，没有的话，再出栈该节点的根节点，比如目前节点是4，右子树没有了，出栈根节点2

4）根节点的左子树遍历完毕，开始遍历1的右子树，先出栈根节点1，同理遍历右子树

复杂度分析

• 时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

• 空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

3.代码

/ 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[] inorderTraversal2 (TreeNode root) {if (null == root) {return new int[0];}List<Integer> list = new ArrayList();inorderTraversal2(list, root);return list.stream().mapToInt(Integer::valueOf).toArray();}public void inorderTraversal2 (List<Integer> list, TreeNode root) {if (null == root) {return;}inorderTraversal2(list, root.left);list.add(root.val);inorderTraversal2(list, root.right);}/非递归算法*/public int[] inorderTraversal (TreeNode root) {if (root == null) {return new int[0];}List<Integer> list = new ArrayList<>();TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();TreeNode top = null;while (cur != null || !stack.isEmpty()) {//把左节点所有左节点入栈while (cur != null) {stack.push(cur);cur = cur.left;}//出栈top = stack.pop();list.add(top.val);cur = top.right;}int size = list.size();int[] arr = new int[size];for (int i = 0; i < size; i++) {arr[i] = list.get(i);}return arr;}
}