题目：给定一个二叉树的根节点 root，返回它的 中序 遍历。
链接：力扣 Leetcode—中级算法—树和图—二叉树的中序遍历.
示例 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]
标签：栈、树、深度优先搜寻、二叉树
思路 ：二叉树的中序遍历，依照拜访左子树——根节点——右子树的形式遍历这棵树，而在拜访左子树或者右子树的时候咱们依照同样的形式遍历，直到遍历完整棵树。因而整个遍历咱们能够间接用 递归 函数来模仿这一过程。或者咱们也能够用 迭代 来解决问题，先将整颗树怼进去，在把所有的左子树怼进去，而后遍历左子树，间接右边的最下边。因为先进后出，拿到了最上面的左节点，也怼到数组里，看以右节点为根的还有没有左节点，有就回到下面第 1 步，没有就走第 3 步，把根节点怼进去，在怼右节点。
递归 Go 代码如下：
package main
import "fmt"
// TreeNode Definition for a binary tree node.
type TreeNode struct {
Val int // 根
Left *TreeNode // 左节点
Right *TreeNode // 右节点
}
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
}
func main() {// 测试用例 root = [1,null,2,3]
root := &TreeNode{1, nil, nil}
root.Right = &TreeNode{2, nil, nil}
root.Right.Left = &TreeNode{3, nil, nil}
res := inorderTraversal(root)
fmt.Printf("res is: %v\n", res)
}提交截图 ：
迭代 Go 代码如下：
package main
import "fmt"
// TreeNode Definition for a binary tree node.
type TreeNode struct {
Val int // 根
Left *TreeNode // 左节点
Right *TreeNode // 右节点
}
func inorderTraversal(root *TreeNode) (res []int) {
// 定义一个栈，栈存的就是一棵树
var stack []*TreeNode
for root != nil || len(stack) > 0 {
for root != nil {
// 1. 先将整颗树怼进去，在把所有的左子树怼进去
stack = append(stack, root)
// 2. 遍历左子树，间接右边的最下边
root = root.Left
}
// 3. 因为先进后出，拿到了最上面的左节点
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 4. 怼到数组里
res = append(res, root.Val)
//5. 看以右节点为根的还有没有左节点，有就回到下面第 1 步，没有就走第 3 步，把根节点
root = root.Right
}
return
}
func main() {// 测试用例 root = [1,null,2,3]
root := &TreeNode{1, nil, nil}
root.Right = &TreeNode{2, nil, nil}
root.Right.Left = &TreeNode{3, nil, nil}
res := inorderTraversal(root)
fmt.Printf("res is: %v\n", res)
}
提交截图：