【golang 必备算法】二叉树篇（一）

方法一：递归

func preorderTraversal(root *TreeNode) []int {
  arr:=[]int{} 
    dfs(root,&arr)	//传地址
return arr
}

func dfs(root *TreeNode,arr *[]int){
 if root==nil{
        return
    }
      *arr=append(*arr,root.Val)

   dfs(root.Left,arr)
   dfs(root.Right,arr)

    return 
}

方法二： 迭代，栈

func preorderTraversal(root *TreeNode) []int {
    if root==nil{
        return []int{}
    }
    stack:=make([]*TreeNode,0)
    arr:=[]int{}
    stack=append(stack,root)
    for len(stack)>0{ 
             temp:=stack[len(stack)-1]  //保存栈顶元素
             //先出栈再加节点
              stack=stack[:len(stack)-1]

                arr=append(arr,temp.Val)
          //先放右节点再放左节点，因为用的是栈，先入后出
          if temp.Right!=nil{
            stack=append(stack,temp.Right)
        }
         if temp.Left!=nil{
            stack=append(stack,temp.Left)
        }
        
    }
    return arr

}

func postorderTraversal(root *TreeNode) []int {
  arr:=[]int{} 
    dfs(root,&arr)	//传地址
return arr
}

func dfs(root *TreeNode,arr *[]int){
 if root==nil{
        return
    }

   dfs(root.Left,arr)
   dfs(root.Right,arr)
     *arr=append(*arr,root.Val)
    return 
}

func  inorderTraversal(root *TreeNode) []int {
  arr:=[]int{} 
    dfs(root,&arr)	//传地址
return arr
}

func dfs(root *TreeNode,arr *[]int){
 if root==nil{
        return
    }

    dfs(root.Left,arr)
    *arr=append(*arr,root.Val)
    dfs(root.Right,arr)
    return 
}

方法一：递归

func levelOrder(root *TreeNode) [][]int {

return dfs([][]int{},root,0)
}

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

    if len(res)==l{
        res=append(res,[]int{root.Val})
    }else{
        res[l]=append(res[l],root.Val)
    }
    res=dfs(res,root.Left,l+1)
    res=dfs(res,root.Right,l+1)

    return res
}

方法二：bfs，队列实现

具体步骤如下：

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

     queue=append(queue,root)
    for len(queue)>0{
        l:=len(queue)
              arr=[]int{}
        for i:=0;i<l;i++{
            if queue[0]==nil{
                queue=queue[1:]
                continue
            }
            queue=append(queue,queue[0].Left)
            queue=append(queue,queue[0].Right)
        
		//将队列第一个元素弹出
        arr=append(arr,queue[0].Val)
        queue=queue[1:]
        }
       res=append(res,arr)
    }

    return res[:len(res)-1]		//最后会多加一个空切片，将其删掉

}

func invertTree(root *TreeNode) *TreeNode {
    if root==nil{
        return root
    }
        t:=root.Left
      root.Left=root.Right
      root.Right=t
   
    invertTree(root.Left)
    invertTree(root.Right)
    return root

}

在层序遍历基础上得到二维数组res

取二维数组每层的最后一个组成数组输出

func rightSideView(root *TreeNode) []int {
    if root==nil{
        return []int{}
    }
    queue:=make([]*TreeNode,0)
    queue=append(queue,root)
    res:=[][]int{}
    var arr []int
    q:=[]int{}

    for len(queue)>0{
        l:=len(queue)
        arr=[]int{}
    for i:=0;i<l;i++{
        if queue[0].Left!=nil{
            queue=append(queue,queue[0].Left)
        }
        if queue[0].Right!=nil{
            queue=append(queue,queue[0].Right)
        }
        arr=append(arr,queue[0].Val)
        queue=queue[1:]
    }
    res=append(res,arr)
    }
 
    for i:=0;i<len(res);i++{
        q=append(q,res[i][len(res[i])-1])
    }

return q
}

func isSymmetric(root *TreeNode) bool {

if root==nil{
    return true
}
return dfs(root.Left,root.Right)

}

func dfs(left *TreeNode,right *TreeNode)bool{
    if left==nil && right==nil{
        return true
    }
    if left!=nil && right==nil{
        return false
    }
    if right!=nil && left==nil{
        return false
    }
    if left.Val != right.Val{
        return false
    }
    return dfs(left.Left,right.Right) && dfs(left.Right,right.Left)
}

func maxDepth(root *TreeNode) int {
       if root==nil{
        return 0
    }
    return max(maxDepth(root.Left),maxDepth(root.Right))+1

}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

二叉树层序遍历 变种

func minDepth(root *TreeNode) int {
    if root==nil{
        return 0
    }
    queue:=make([]*TreeNode,0)
    queue=append(queue,root)
    n:=1

    for len(queue)>0{
        l:=len(queue)
        for i:=0;i<l;i++{
            if queue[0].Left==nil && queue[0].Right==nil{
                return n
            }
            if queue[0].Left!=nil {
                queue=append(queue,queue[0].Left)
            }
            if queue[0].Right!=nil{
                queue=append(queue,queue[0].Right)
            }
            queue=queue[1:]
        }
        n++
    }
   return 0
}

func isBalanced(root *TreeNode) bool {
     if root == nil {
        return true
    }
     if jue(dfs(root.Left)-dfs(root.Right))>1{
         return false
     }
     return isBalanced(root.Left) && isBalanced(root.Right)
  

}

func dfs(root *TreeNode)int{
      if root == nil {
        return 0
    }
    return max(dfs(root.Left),dfs(root.Right))+1
}

func jue(a int)int{
    if a<0{
        return -1*a
    }
    return a
}

func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}

方法一：递归

func binaryTreePaths(root *TreeNode) []string {
    if root == nil{
        return []string{}
    }
    res:=[]string{}
    dfs(root,&res,"")
    return res
}

func dfs(root *TreeNode,res *[]string,a string) {
    ans:=a
   if root.Left==nil && root.Right==nil{
       v:=ans+strconv.Itoa(root.Val)
       *res=append(*res,v)
       return 
    }
    ans=ans+strconv.Itoa(root.Val)+"->"
    if root.Left!=nil{  
        dfs(root.Left,res,ans)
    }
    if root.Right!=nil{
         dfs(root.Right,res,ans)
    }
    return 
}