给定一个二叉树，返回它的 前序 遍历。
image.png
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
package leetcode
import "zheng/sort"
/*
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
*/
/**
- Definition for a binary tree node.
- type TreeNode struct {
Val intLeft *TreeNodeRight *TreeNode- }
*/
func preorderTraversal(root TreeNode) []int {
stack := sort.NewStack()
// 数组
list := make([]int, 0)
for {
list = append(list, root.Val)
if root.Right != nil {
stack.Push(root.Right)
}
if root.Left != nil {
root = root.Left
} else {
if stack.Len() != 0 {
root = stack.Pop().(TreeNode)
} else {
root = nil
}
}
if root == nil {
break
}
}
return list
}
package sort
import "container/list"
type Stack struct {
list *list.List
}
func NewStack() *Stack {
list := list.New()
return &Stack{list}
}
func (stack *Stack) Push(value interface{}) {
stack.list.PushBack(value)
}
func (stack *Stack) Pop() interface{} {
e := stack.list.Back()
if e != nil {
stack.list.Remove(e)
return e.Value
}
return nil
}
func (stack *Stack) Peak() interface{} {
e := stack.list.Back()
if e != nil {
return e.Value
}
return nil
}
func (stack *Stack) Len() int {
return stack.list.Len()
}
func (stack *Stack) Empty() bool {
return stack.list.Len() == 0
}
