给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：
144.二叉树的前序遍历 - 图1

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

示例 2：

输入：root = []
输出：[]

示例 3：

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

示例 4：
144.二叉树的前序遍历 - 图2

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

示例 5：
144.二叉树的前序遍历 - 图3

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


提示：

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

  • -100 <= Node.val <= 100


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

    解法一：递归

    func preorderTraversal(root *TreeNode) []int {
  res := []int{}
  var preorderTraversal func(root *TreeNode)

  preorderTraversal = func(root *TreeNode) {
      if root == nil {
          return
      }
      res = append(res, root.Val)
      preorderTraversal(root.Left)
      preorderTraversal(root.Right)
  }
  preorderTraversal(root)
  return res
}

    解法二：迭代一

  • 初始化栈，根节点入栈

  • 弹出栈顶元素，处理栈顶元素
  • 判断栈顶元素的右子树非空，将右子树入栈
  • 判断栈顶元素的左子树非空，将左子树入栈
    func preorderTraversal(root *TreeNode) []int {
  res := []int{}
  if root == nil {
      return res
  }
  stack := []*TreeNode{root}
  for len(stack) > 0 {
      var top *TreeNode
      top, stack = stack[len(stack)-1], stack[:len(stack)-1]
      res = append(res, top.Val)
      if top.Right != nil {
          stack = append(stack, top.Right)
      }
      if top.Left != nil {
          stack = append(stack, top.Left)
      }
  }
  return res
}

    解法三：迭代二

    套模版！！！
    func preorderTraversal(root *TreeNode) []int {
  res := []int{}
  stack := []*TreeNode{}
  top := root
  for len(stack) > 0 || top != nil {
      for top != nil {
          res = append(res, top.Val)
          stack = append(stack, top.Right)
          top = top.Left
      }
      top, stack = stack[len(stack)-1], stack[:len(stack)-1]
  }
  return res
}