1.问题
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1
图1
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2
输入：root = []
输出：[]
示例 3
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
2.解题思路
2.1 递归
类似【LeetCode】144.二叉树的前序遍历，中序遍历规则为 左-根-右，只要对前序遍历-递归稍作调整，即可实现；
复杂度分析
时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
2.2 迭代（栈）
若利用栈（迭代思想），则需要调整下入栈顺序，遍历顺序
1）先遍历根节点，入栈
图2
2）循环遍历左子树
图3
图4
3）到达最左边，出栈，遍历该节点右子树，入栈，没有的话，再出栈该节点的根节点，比如目前节点是4，右子树没有了，出栈根节点2
图5
图6
图7
图8
4）根节点的左子树遍历完毕，开始遍历1的右子树，先出栈根节点1，同理遍历右子树
图9
图10
图11
图12
图13
图14
复杂度分析
时间复杂度：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;
}
}
