题目：给定一个二叉树的根节点 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 mainimport "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 mainimport "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)}提交截图：