题目描述
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[2,1]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶:
递归算法很简单，你可以通过迭代算法完成吗？
题目分析
首先，我们要明确一个概念：二叉树的中序遍历是什么？
答案：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
思路讲解
进阶中也给出了我们提示，使用递归算法能非常简单的解题，因为二叉树中序遍历的过程天然具有递归调用的特点。
具体执行思路请看下面代码段中的注释。
AC代码
func inorderTraversal(root *TreeNode) (res []int) { //自定义函数 方便进行递归调用 var inorder func(node *TreeNode) inorder = func(node *TreeNode) { //如果根节点为空，直接返回空数组 if node == nil { return } //传入根节点的左节点 inorder(node.Left) //追加切片 res = append(res, node.Val) //传入根节点的右节点 inorder(node.Right) } inorder(root) return }
运行结果
总结
复杂度分析
时间复杂度：O(n)，其中 n 为二叉树节点的个数。
空间复杂度：O(n)，空间复杂度取决于递归的栈深度。
