遍历

go 实现二叉树前序、中序、后序、层级遍历

type TreeNode struct {
    Val  int    
    Left  *TreeNode    
    Right *TreeNode 
}
func main(){
   root := &TreeNode{Val: 1}
   root.Left = &TreeNode{Val: 2}
   root.Right = &TreeNode{Val: 3}
   root.Left.Left = &TreeNode{Val: 4}
   root.Left.Right = &TreeNode{Val: 5}
   root.Right.Left = &TreeNode{Val: 6}
   root.Right.Right = &TreeNode{Val: 7}
   root.Left.Right.Left = &TreeNode{Val: 8}
   root.Right.Left.Right = &TreeNode{Val: 9}
   PreOrder(root)  
}

前序遍历
// 递归实现

// 递归实现 
func PreOrder(root  *TreeNode) []int {
    res := []int{}
   if root == nil {
      return res 
   }
       res = append(res,root.Val)
    res = append(res,PreOrder(root.Left)...)
    res = append(res,PreOrder(root.Right)...)
    return res 
}



// 遍历实现
// 思路
//前序遍历迭代思路
//1， 首先申请一个新的栈，记为stack
//2，首先声明一个节点tree，让其指向node节点
//3，如果tree 不为空，将tree的值打印，并将tree入栈,然后让tree指向tree的右节点
//4，重复步骤3，直到tree为空
//5，然后出战，让tree 指向tree的右孩子
//6，重复步骤3，直到stack为空

func PreOrder(root *TreeNode) []interface{} {
   res := make([]int,0)
   stack := []*TreeNode{}

   for  root != nil || len(stack) != 0{
      if root != nil {
         res = append(res,root.Val)
         stack = append(stack,root)
         root = root.Left
      } else {
         root = stack[len(stack)-1]
         stack = stack[:len(stack)-1]
         root = root.Right
      }
   }
   return res
}

中序遍历

// 递归实现
func InOrder(root  *TreeNode) []int {
   if root == nil {
      return res
   }
    res = append(res,InOrder(root.Left)...)
       res = append(res,root.Val)
    res = append(res,InOrder(root.Right)...)
    return res 
}


//迭代实现
func  InOrder(root *TreeNode) []int {
   res := []int{}
   stack := []*TreeNode{}

   for root != nil || len(stack) != 0 {
      if root != nil {
         stack = append(stack,root)
         root = root.Left
      }else {
         root = stack[len(stack)-1]
         res = append(res,root.Val)
         stack = stack[:len(stack)-1]
         root = root.Right
      }
   }
   return res
}

后序遍历

// 递归实现
func PostOrder(root  *TreeNode) []int {
    res := []int{}
   if root == nil {
      return res 
   }
    res = append(res,InOrder(root.Left)...)
    res = append(res,root.Val)
    res = append(res,InOrder(root.Right)...)
   return res 
}

//迭代实现一

func PostOrder(root *TreeNode) []int {
   res := []int{}
   stack := []*TreeNode{}
   var lastvisit  *TreeNode

   for root != nil || len(stack) != 0 {
      for root != nil {
         stack = append(stack,root)
         root = root.Left
      }
      if len(stack) != 0 {
         root = stack[len(stack)-1]
         stack = stack[:len(stack)-1]

         if root.Right == nil || root.Right == lastvisit {
            res = append(res,root.Val)
            lastvisit = root
            root = nil
         } else {
            stack = append(stack,root)
            root = root.Right
         }
      }
   }
   return res
}


//迭代实现二
func PostOrder(root *TreeNode)   {
   stack1,stack2 := []*TreeNode{},[]*TreeNode{}

   stack1 = append(stack1,root)

   for len(stack1) > 0 {
      root = stack1[len(stack1)-1]
      stack1 = stack1[:len(stack1)-1]

      stack2 = append(stack2,root)

      if  root.left != nil {
         stack1 = append(stack1,root.Left)
      }
      if root.right != nil {
         stack1 = append(stack1,root.Right)
      }
   }
    for i:=len(stack2)-1;i>=0;i-- {
      fmt.Print(i.Val," ")
   }
}

层级遍历

// 思路
//1, 首先申请一个新的队列，记为queue；
//2,将头结点head压入queue中；
//3,每次从queue中出队，记为node，然后打印node值，如果node左孩子不为空，则将左孩子入队；如果node的右孩子不为空，则将右孩子入队；
//4, 重复步骤3，直到queue为空

//迭代实现 
func LevelOrder(root *TreeNode)  []int {
    // 收集结果
   res := []int{}
   // queue 创建队列 
   Queue := []*TreeNode{}
   // 把root 添加到队列中
   Queue = append(Queue,root)
   for len(Queue) > 0 {
       // 取出队列的头元素，把Val值添加到res中，pop 头元素
      root = Queue[0]
      res = append(res,root.Val)
      Queue = Queue[1:]
      // 加入root元素的左孩子和右孩子到队列
      if root.Left != nil  {
         Queue = append(Queue,root.Left)
      }
      if root.Right != nil  {
         Queue = append(Queue,root.Right)
      }
   }
   return res
}

// 递归

var res [][]int

func levelOrder(root *TreeNode) [][]int {
    if root == nil{
        return nil
    }
    res = make([][]int, 0)
    dfs(root, 0)
    return res
}

func dfs(root *TreeNode, level int){
    if root == nil{
        return
    }
    if level == len(res){
        res = append(res, []int{})
    }
    res[level] = append(res[level], root.Val)
    dfs(root.Left, level+1)
    dfs(root.Right,level+1)
}