# 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例1：
输入：root = [1,null,2,3]
输出：[1,3,2]
1
2
2
输入：root = []
输出：[]
1
2
2
输入：root = [1]
输出：[1]
1
2
2
示例2：
输入：root = [1,2]
输出：[2,1]
1
2
2
示例3：
输入：root = [1,null,2]
输出：[1,2]
1
2
2
# 思路
二叉树有天然的递归性质，前序遍历：根左右，中序遍历：左根右，后续遍历：左右根；
inorder(root) 遍历节点；inorder(root.left)遍历左子树；inorder(order.right)遍历右子树；
遍历完根节点，遍历子节点，遇到空节点结束。
var inorderTraversal = function(root){
// 定义一个空数组
const res = [];
const inorder = (root) => {
// 如果遇到空节点，返回nul
if(!root) return;
// 中序遍历：左根右遍历
inorder(root.left);
res.val(root);
inorder(root.right);
}
inorder(root);
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
时间复杂度：O(n)O(n)，其中 nn 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n)O(n) 的级别。