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

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

news 2025/8/23 9:13:55

前言

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

内容

一、二叉树的右视图

199.二叉树的右视图

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

广度优先搜索

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

func rightSideView(root *TreeNode) []int {var res []intif 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 []float64curLevel:=[]*TreeNode{root}for len(curLevel)>0{sum:=0nextLevel:=[]*TreeNode{}for _,node:=range curLevel{sum+=node.Valif 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 [][]intif root==nil{return res}curLevel:=[]*Node{root}for len(curLevel)>0{level:=[]int{}temp:=curLevelcurLevel=nilfor _,node:=range temp{level=append(level,node.Val)curLevel=append(curLevel,node.Children...)}//node.Children... 是一个可变参数，可以接收任意数量的子节点，并将它们存储在一个列表中。res=append(res,level)}return res
}