📑 题目：144. 二叉树的前序遍历

🚀 本题 LeetCode 传送门

题目大意

先根遍历一颗树。

解题思路

两种递归的实现方法，见代码。

代码

package leetcode
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 解法一 递归
func preorderTraversal(root *TreeNode) []int {
 res := []int{}
 if root != nil {
  res = append(res, root.Val)
  tmp := preorderTraversal(root.Left)
  for _, t := range tmp {
   res = append(res, t)
  }
  tmp = preorderTraversal(root.Right)
  for _, t := range tmp {
   res = append(res, t)
  }
 }
 return res
}
// 解法二 递归
func preorderTraversal1(root *TreeNode) []int {
 var result []int
 preorder(root, &result)
 return result
}
func preorder(root *TreeNode, output *[]int) {
 if root != nil {
  *output = append(*output, root.Val)
  preorder(root.Left, output)
  preorder(root.Right, output)
 }
}
// 解法三 非递归，用栈模拟递归过程
func preorderTraversal2(root *TreeNode) []int {
 if root == nil {
  return []int{}
 }
 stack, res := []*TreeNode{}, []int{}
 stack = append(stack, root)
 for len(stack) != 0 {
  node := stack[len(stack)-1]
  stack = stack[:len(stack)-1]
  if node != nil {
   res = append(res, node.Val)
  }
  if node.Right != nil {
   stack = append(stack, node.Right)
  }
  if node.Left != nil {
   stack = append(stack, node.Left)
  }
 }
 return res
}