一、递归版本

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 根 - 左 - 右
func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    rs := make([]int , 0 )
    
    // 根
    rs = append(rs, root.Val)
    
    // left
    if root.Left != nil {
        leftData := preorderTraversal(root.Left)
        rs = append(rs, leftData...)
    }
    
    // right
    if root.Right != nil {
        RightData := preorderTraversal(root.Right)
        rs = append(rs, RightData...)
    }
    
    return rs
}

二、非递归版本

思路：利用栈先进后出的特性

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type NodeStack struct {
    data []*TreeNode
}

func (h* NodeStack) Push(d *TreeNode){
    if h.data == nil {
        h.data = make([]*TreeNode, 0)
    }
    
    h.data = append(h.data, d)
}

func (h* NodeStack) Pop()*TreeNode {
    dataLen := len(h.data)
    if dataLen == 0 {
        return nil
    }
   
    d := h.data[dataLen - 1]
  
    h.data = h.data[:dataLen-1]
    
    return d
}

// 根 - 左 - 右
func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    
    rs := make([]int , 0 )
    q := new(NodeStack)
    for{
        if root == nil {
            root = q.Pop()
        }
        
        if root == nil {
            break
        }
     
        rs = append(rs, root.Val) // 记录根节点
        
        if root.Right != nil {
            q.Push(root.Right)
        }
        
        root = root.Left
    }
   
    return rs
}