给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]示例 4：
输入：root = [1,2]
输出：[1,2]示例 5：
输入：root = [1,null,2]
输出：[1,2]提示：
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
解题：
func preorderTraversal(root *TreeNode) []int {
var r []int
if root == nil {
return r
}
var bfs func(node *TreeNode)
bfs = func(node *TreeNode) {
r = append(r, node.Val)
if node.Left != nil {
bfs(node.Left)
}
if node.Right != nil {
bfs(node.Right)
}
}
bfs(root)
return r
}官方解答：
1.递归
func preorderTraversal(root *TreeNode) (vals []int) {
var preorder func(*TreeNode)
preorder = func(node *TreeNode) {
if node == nil {
return
}
vals = append(vals, node.Val)
preorder(node.Left)
preorder(node.Right)
}
preorder(root)
return
}2.迭代
func preorderTraversal(root *TreeNode) (vals []int) {
stack := []*TreeNode{}
node := root
for node != nil || len(stack) > 0 {
for node != nil {
vals = append(vals, node.Val)
stack = append(stack, node)
node = node.Left
}
node = stack[len(stack)-1].Right
stack = stack[:len(stack)-1]
}
return
}3.Morris 遍历
func preorderTraversal(root *TreeNode) (vals []int) {
var p1, p2 *TreeNode = root, nil
for p1 != nil {
p2 = p1.Left
if p2 != nil {
for p2.Right != nil && p2.Right != p1 {
p2 = p2.Right
}
if p2.Right == nil {
vals = append(vals, p1.Val)
p2.Right = p1
p1 = p1.Left
continue
}
p2.Right = nil
} else {
vals = append(vals, p1.Val)
}
p1 = p1.Right
}
return
}