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?
思路：
二叉树的先序遍历，递归求解和迭代，迭代使用list容器的链表代替栈来做
代码：
go：
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// recursive
/*func preorderTraversal(root *TreeNode) []int {
var res = make([]int, 0)
recursive(root, &res)
return res
}
func recursive(root *TreeNode, res *[]int) {
if root == nil {
return
}
*res = append(*res, root.Val)
recursive(root.Left, res)
recursive(root.Right, res)
}
*/
// iterative
func preorderTraversal(node *TreeNode) []int {
var res []int
var stack []*TreeNode
for node != nil || len(stack) != 0 {
for node != nil {
res = append(res, node.Val)
stack = append(stack, node)
node = node.Left
}
if len(stack) != 0 {
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
node = node.Right
}
}
return res
}
