var q Queue
func initQueue() *Queue {
  if q.nodeList == nil {
    q = Queue{}
    q.new()
  }
  return &q
}
type Queue struct {
  nodeList [] *BiTreeNode
}
type IQueue interface {
  new() *Queue
  enqueue(node *BiTreeNode)
  dequeue() *BiTreeNode
  isEmpty() bool
  size() int
}
func (q *Queue) new() *Queue {
  q.nodeList = []*BiTreeNode{}
  return q
}
func (q *Queue) enqueue(node *BiTreeNode) {
  q.nodeList = append(q.nodeList, node)
}
func (q *Queue) dequeue() *BiTreeNode {
  if 0 == len(q.nodeList) {
    return nil
  } else {
    item := q.nodeList[0]
    q.nodeList = q.nodeList[1:len(q.nodeList)]
    return item
  }
}
func (q *Queue) isEmpty() bool {
  return len(q.nodeList) == 0
}
func (q *Queue) size() int {
  return len(q.nodeList)
}

func createBiTree(nodes [] int) *BiTreeNode {
  //var root BiTreeNode
  if nil != nodes && 0 != len(nodes) {
    root := BiTreeNode{}
    root.val = nodes[0]
    //nodes = nodes[1:len(nodes)]
    q := initQueue()
    q.enqueue(&root)
    var len int = len(nodes)
    for i := 1; i < len; {
      temp := q.dequeue()
      if -1 != nodes[i] {
        left := BiTreeNode{}
        left.val = nodes[i]
        q.enqueue(&left)
        temp.left = &left
      }
      i++
      if -1 != nodes[i] {
        right := BiTreeNode{}
        right.val = nodes[i]
        q.enqueue(&right)
        temp.right = &right
      }
      i++
    }
    return &root
  }
  return nil
}

func preOrderBiTree(root *BiTreeNode) {
  if nil != root {
    fmt.Println((*root).val)
    preOrderBiTree((*root).left)
    preOrderBiTree((*root).right)
  }
}

type BiTreeNode struct {
  val   int
  left  *BiTreeNode
  right *BiTreeNode
}