给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：
94.二叉树的中序遍历 - 图1

  1. 输入：root = [1,null,2,3]
  2. 输出：[1,3,2]

示例 2：

  1. 输入：root = []
  2. 输出：[]

示例 3：

  1. 输入：root = [1]
  2. 输出：[1]

示例 4：
94.二叉树的中序遍历 - 图2

  1. 输入：root = [1,2]
  2. 输出：[2,1]

示例 5：
94.二叉树的中序遍历 - 图3

  1. 输入：root = [1,null,2]
  2. 输出：[1,2]


提示：

  • 树中节点数目在范围 [0, 100] 内

  • -100 <= Node.val <= 100


    进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解法一：递归

  1. func inorderTraversal(root *TreeNode) []int {
  2.     res := []int{}
  3.     var inorder func(root *TreeNode)
  4.     inorder = func(root *TreeNode) {
  5.         if root == nil {
  6.             return
  7.         }
  8.         inorder(root.Left)
  9.         res = append(res, root.Val)
  10.         inorder(root.Right)
  11.     }
  12.     inorder(root)
  13.     return res
  14. }

解法二：迭代

中序：左、根、右
需要借助 栈 来实现。
对于每个节点 A， 我们需要先将 A 入栈，然后遍历其左子树，接着访问 A，最后再遍历右子树。
所以就是 A 入栈，A 的左节点入栈（直到没有左节点为止），栈顶出栈且栈顶的右节点入栈

  1. func inorderTraversal(root *TreeNode) []int {
  2.     res := []int{}
  3.     stack := []*TreeNode{}
  4.     top := root
  5.     for len(stack) > 0 || top != nil {
  6.         for root != nil {
  7.             stack = append(stack, top)
  8.             top = top.Left
  9.         }
  10.         top, stack = stack[len(stack)-1], stack[:len(stack)-1]
  11.         res = append(res, top.Val)
  12.         top = top.Right
  13.     }
  14.     return res
  15. }