一、题目描述
给定一个二叉树的根节点 root ，返回它的中序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
二、题目分析
首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
-
递归法
从上述过程中我们可以看到整个遍历过程天然具有 递归 的性质，我们可以直接用递归函数来模拟这一过程。
-
迭代法
上述递归函数我们也可以用迭代的方式实现，两种方式是等价的。
区别在于上述递归的过程隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同。
三、我的题解
递归法：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
if root == nil{
return nil
}
var re []int
if root.Left == nil && root.Right == nil{
re = []int{root.Val}
return re
}else{
re = append(re, inorderTraversal(root.Left)...) //递归
re = append(re, root.Val)
re = append(re, inorderTraversal(root.Right)...)
return re
}
}
复杂度分析：
-
时间复杂度：O(n)，其中 nn 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
-
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
评判结果：
