golang刷leetcode 二叉树的遍历

一.前序遍历

　　　前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。

二.中序遍历

　　中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。

三.后序遍历

　后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。

总结：由根节点在前中后决定前中后序，三种遍历代码逻辑一样，只是打印位置不一样，非递归方式后续遍历需要两个栈后进先出打印

解决方式

1，递归

func inorderTraversal(root *TreeNode){
    if root!=nil{
         //前序在这里打印
        inorderTraversal(root.Left)
        //中序在这里打印
        r:=inorderTraversal(root.Right)
        //后序在这里打印
    }
}

2，非递归

func inorderTraversal(root *TreeNode){
    var s Stack   
    cur:=root
    for !s.empty() || cur!=nil{
        for cur!=nil{
             //前序遍历，在这里打印value
             s.push(cur)
             cur=cur.Left
        }
        if !s.empty(){//注意这里是判断不是循环
            cur=s.pop()
             //中序遍历，在这里打印value
            cur=cur.Right
            //后续遍历在这里打印但是，需要加个标识，是否进过栈，进过才打印
        }
    }
}

golang中序遍历实现例子

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var m []int
    if root!=nil{
        l:=inorderTraversal(root.Left)
        m=append(l,root.Val)
        r:=inorderTraversal(root.Right)
        m=append(m,r...)
    }
    return m
}

非递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var m []int
    var s Stack   
    cur:=root
    for !s.empty() || cur!=nil{
        for cur!=nil{
             s.push(cur)
            cur=cur.Left
        }
        if !s.empty(){
            cur=s.pop()
            m=append(m,cur.Val)
            cur=cur.Right
        }
    }
    return m
}

type Stack struct{
    data []*TreeNode
}

func (s*Stack)empty() bool{
    return len(s.data)==0
}
func (s* Stack)push(node* TreeNode){
    s.data=append( s.data,node)
}

func (s*Stack)pop()(node* TreeNode){
    if len(s.data)==0{
        return nil
    }
    node=s.data[len(s.data)-1]
    s.data=s.data[0:len(s.data)-1]
    return node
}
func (s*Stack)printSelf(){
    for i:=0;i<len(s.data);i++{
        fmt.Print((*s.data[i]).Val)
    }
    fmt.Println("")
}

后序遍历＋将list转化成二叉树

package main

import (
  "fmt"
  "strconv"
)

func main() {
  h := sliceToTree(parseSlice([]string{"1", "null", "2", "3", "null", "5", "4"}))
  walkTree(h)
  fmt.Println(inorderTraversal(h))
}

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func walkTree(h *TreeNode) {
  if h != nil {
    walkTree(h.Left)
    walkTree(h.Right)
    fmt.Println(h.Val)
  }
}
func parseSlice(vals []string) []*TreeNode {
  if len(vals) < 1 {
    return nil
  }
  st := make([]*TreeNode, len(vals))
  for i := 0; i < len(vals); i++ {
    if vals[i] == "null" {
      st[i] = nil
      continue
    }
    i32, e := strconv.ParseInt(vals[i], 10, 32)
    if e != nil {
      st[i] = nil
      continue
    }
    st[i] = &TreeNode{int(i32), nil, nil}
  }
  return st
}
func sliceToTree(st []*TreeNode) (h *TreeNode) {
  if len(st) < 1 {
    return nil
  }
  if len(st) == 1 || st[0] == nil {
    return st[0]
  }
  h, s := fillChild(st[0], st[1:len(st)])
  cur := h
  for len(s) > 0 {
    if cur.Left != nil && cur.Right != nil {
      cur.Left, s = fillChild(cur.Left, s)
      cur.Right, s = fillChild(cur.Right, s)
      cur = cur.Left
      continue
    }
    if cur.Left != nil {
      cur.Left, s = fillChild(cur.Left, s)
      cur = cur.Left
      continue
    }
    if cur.Right != nil {
      cur.Right, s = fillChild(cur.Right, s)
      cur = cur.Right
    }
  }
  return h

}

func fillChild(h *TreeNode, st []*TreeNode) (*TreeNode, []*TreeNode) {
  if len(st) < 1 {
    return h, nil
  }
  if len(st) == 1 {
    h.Left = st[0]
    return h, nil
  }
  if len(st) == 2 {
    h.Left = st[0]
    h.Right = st[1]
    return h, nil
  }
  h.Left = st[0]
  h.Right = st[1]
  return h, st[2:len(st)]
}

func inorderTraversal(root *TreeNode) []int {
  var m []int
  var s Stack
  var s2 Stack
  cur := root
  for !s.empty() || cur != nil {
    for cur != nil {
      s.push(cur)
      s2.push(cur)
      cur = cur.Right
    }
    if !s.empty() {
      cur = s.pop()
      cur = cur.Left
    }
  }
  for !s2.empty() {
    cur = s2.pop()
    if cur != nil {
      m = append(m, cur.Val)
    }
  }
  return m
}

type Stack struct {
  data []*TreeNode
}

func (s *Stack) empty() bool {
  return len(s.data) == 0
}
func (s *Stack) push(node *TreeNode) {
  s.data = append(s.data, node)
}

func (s *Stack) pop() (node *TreeNode) {
  if len(s.data) == 0 {
    return nil
  }
  node = s.data[len(s.data)-1]
  s.data = s.data[0 : len(s.data)-1]
  return node
}
func (s *Stack) printSelf() {
  for i := 0; i < len(s.data); i++ {
    fmt.Print((*s.data[i]).Val)
  }
  fmt.Println("")
}

层序遍历：

队列实现的基本思路：遍历从根节点开始，首先将根节点入队，然后执行循环：节点出队，访问（访问）根节点，将左儿子入队，将右儿子入队，直到队列为空停止

package main

import (
  "fmt"
  "strconv"
)

func main() {
  fmt.Println("Hello, 世界")
  h := sliceToTree(parseSlice([]string{"1", "null", "2", "3", "null", "5", "4"}))
  walkTree(h)
  fmt.Println(LevelOrderTraversal(h))
}

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func walkTree(h *TreeNode) {
  if h != nil {
    fmt.Println(h.Val)
    walkTree(h.Left)
    walkTree(h.Right)
  }
}
func parseSlice(vals []string) []*TreeNode {
  if len(vals) < 1 {
    return nil
  }
  st := make([]*TreeNode, len(vals))
  for i := 0; i < len(vals); i++ {
    if vals[i] == "null" {
      st[i] = nil
      continue
    }
    i32, e := strconv.ParseInt(vals[i], 10, 32)
    if e != nil {
      st[i] = nil
      continue
    }
    st[i] = &TreeNode{int(i32), nil, nil}
  }
  return st
}
func sliceToTree(st []*TreeNode) (h *TreeNode) {
  if len(st) < 1 {
    return nil
  }
  if len(st) == 1 || st[0] == nil {
    return st[0]
  }
  h, s := fillChild(st[0], st[1:len(st)])
  cur := h
  for len(s) > 0 {
    if cur.Left != nil && cur.Right != nil {
      cur.Left, s = fillChild(cur.Left, s)
      cur.Right, s = fillChild(cur.Right, s)
      cur = cur.Left
      continue
    }
    if cur.Left != nil {
      cur.Left, s = fillChild(cur.Left, s)
      cur = cur.Left
      continue
    }
    if cur.Right != nil {
      cur.Right, s = fillChild(cur.Right, s)
      cur = cur.Right
    }
  }
  return h

}

func fillChild(h *TreeNode, st []*TreeNode) (*TreeNode, []*TreeNode) {
  if len(st) < 1 {
    return h, nil
  }
  if len(st) == 1 {
    h.Left = st[0]
    return h, nil
  }
  if len(st) == 2 {
    h.Left = st[0]
    h.Right = st[1]
    return h, nil
  }
  h.Left = st[0]
  h.Right = st[1]
  return h, st[2:len(st)]
}

func LevelOrderTraversal(root *TreeNode) []int {
  var m []int
  if root == nil {
    return m
  }
  var q Queue
  q.push(root)
  for !q.empty() {
    cur := q.pop()
    m = append(m, cur.Val)
    if cur.Left != nil {
      q.push(cur.Left)
    }
    if cur.Right != nil {
      q.push(cur.Right)
    }
  }
  return m
}

type Queue struct {
  data []*TreeNode
}

func (s *Queue) empty() bool {
  return len(s.data) == 0
}
func (s *Queue) push(node *TreeNode) {
  s.data = append(s.data, node)
}

func (s *Queue) pop() (node *TreeNode) {
  if len(s.data) == 0 {
    return nil
  }
  node = s.data[0]
  if len(s.data) == 1 {
    s.data = nil
    return node
  }
  s.data = s.data[1:len(s.data)]
  return node
}
func (s *Queue) printSelf() {
  for i := 0; i < len(s.data); i++ {
    fmt.Print((*s.data[i]).Val)
  }
  fmt.Println("")
}