当前位置：首页 > article >正文

力扣刷题第二十七天--二叉树

article 2024/10/23 5:49:23

前言

题目大同小异，按要求来即可。

内容

一、二叉树的右视图

199.二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

广度优先搜索

取每层最后一个元素，放入结果集

func rightSideView(root *TreeNode) []int {
    var res []int
    if root==nil{
        return res
    }
 
 queue:=list.New()
 queue.PushBack(root)

 for queue.Len()>0{
     length:=queue.Len()
     for i:=0;i<length;i++{
         node:=queue.Remove(queue.Front()).(*TreeNode)
         if node.Left!=nil{
             queue.PushBack(node.Left)
         }
         if node.Right!=nil{
             queue.PushBack(node.Right)
         }
         if i==length-1{
            res=append(res,node.Val)
         }
     }
     
 }
 return res
}

深度优先搜索

func rightSideView(root *TreeNode)(ans []int){
    var dfs func(*TreeNode,int)
    dfs=func(node *TreeNode,depth int){
        if node==nil{
            return 
        }
        if depth==len(ans){
            ans=append(ans,node.Val)
        }
        dfs(node.Right,depth+1)
        dfs(node.Left,depth+1)
    }
    dfs(root,0)
    return
}

二、二叉树的层平均数

637.二叉树的层平均数

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

广度优先搜索

func averageOfLevels(root *TreeNode) []float64 {
    var res []float64
    curLevel:=[]*TreeNode{root}
    for len(curLevel)>0{
        sum:=0
        nextLevel:=[]*TreeNode{}
        for _,node:=range curLevel{
            sum+=node.Val

            if node.Left!=nil{
                nextLevel=append(nextLevel,node.Left)
            }
            if node.Right!=nil{
                nextLevel=append(nextLevel,node.Right)
            }
        
        }
    res=append(res,float64(sum)/float64(len(curLevel)))
       curLevel=nextLevel
    }
    return  res
}

三、N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

广度优先搜素

一个结点有多个孩子，别忘了root为空

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) [][]int {
    var res [][]int
    if root==nil{
        return res
    }
    
    curLevel:=[]*Node{root}
    for len(curLevel)>0{
        
        level:=[]int{}
      temp:=curLevel
      curLevel=nil
      for _,node:=range temp{
          level=append(level,node.Val)
          curLevel=append(curLevel,node.Children...)
      }//node.Children... 是一个可变参数，可以接收任意数量的子节点，并将它们存储在一个列表中。
    
        res=append(res,level)
      
    }
    return res
}