144. 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

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 int
  

• Left *TreeNode
  

• Right *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
}