一、递归

/**
 * 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
    }
    rs := make([]int, 0)
    // left
    if root.Left != nil {
        rs = append(rs, inorderTraversal(root.Left)...)    
    } 
    // 根
    rs = append(rs, root.Val)
    
    // right
    if root.Right != nil {
         rs = append(rs, inorderTraversal(root.Right)...)   
    }
    
    return rs
}

二、非递归版本

// 二叉树中序遍历非递归
// 左-根-右
// 思路:
// 1、将root节点标记为当前节点
// 2、从当前节点开始，将所有left节点，插入栈中
// 3、从栈中取出节点，标记为当前节点值，将当前节点的值记录下来，即为当前需要输出的值
// 4、重复步骤2~3，直到栈为空且当前节点为空
func inorderTraversal(root *TreeNode) []int {
   if root == nil {
      return nil
   }

   if root.Left == nil && root.Right == nil {
      return []int{root.Val}
   }

   rs := make([]int, 0)
   s := new(Stack)

   curNode := root
   for curNode != nil || ! s.IsEmpty() {
      //一直遍历到左子树最下边，边遍历边保存根节点到栈中
      for curNode != nil {
         s.Push(curNode)

         curNode = curNode.Left
      }

      //当p为空时，说明已经到达左子树最下边，这时需要出栈了
      if ! s.IsEmpty() {
         curNode = s.Pop()
         rs = append(rs, curNode.Val)

         curNode = curNode.Right
      }
   }

   return rs
}