0144. Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal#

题目 #

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

``````
Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]

``````

Follow up: Recursive solution is trivial, could you do it iteratively?

代码 #

``````
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
}

``````

Sep 6, 2020