102. 二叉树的层序遍历{学会层序遍历，直接打十个！！}
难度中等1542收藏分享切换为英文接收动态反馈
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
var res [][]int
var res1 []int
var queue []*TreeNode
if root==nil{
return res
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
for size>0{
node:=queue[0]
queue=queue[1:]
res1=append(res1,node.Val)
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
size--
}
res=append(res,res1)
res1=[]int{}
}
return res
}
会了上边的，那么下面几题轻松秒，我要打十个：
107. 二叉树的层序遍历 II
难度中等640收藏分享切换为英文接收动态反馈
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrderBottom(root *TreeNode) [][]int {
var res [][]int
var res1 []int
var queue []*TreeNode
if root==nil{
return res
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
for size>0{
node:=queue[0]
queue=queue[1:]
res1=append(res1,node.Val)
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
size--
}
res=append(res,res1)
res1=[]int{}
}
reverse(res)
return res
}
func reverse(a [][]int) {
l, r := 0, len(a) - 1
for l < r {
a[l], a[r] = a[r], a[l]
l, r = l+1, r-1
}
}
199. 二叉树的右视图
难度中等794收藏分享切换为英文接收动态反馈
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
提示:
- 二叉树的节点个数的范围是
[0,100] -100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) []int {
var res []int
var res1 []int
var queue []*TreeNode
if root==nil{
return res
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
for size>0{
node:=queue[0]
queue=queue[1:]
res1=append(res1,node.Val)
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
size--
}
res=append(res,res1[len(res1)-1])
res1=[]int{}
}
return res
}
637. 二叉树的层平均值
难度简单385收藏分享切换为英文接收动态反馈
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]
提示：
- 树中节点数量在
[1, 104]范围内 -231 <= Node.val <= 231 - 1
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func averageOfLevels(root *TreeNode) []float64 {
var res []float64
var res1 []int
var queue []*TreeNode
if root==nil{
return res
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
for size>0{
node:=queue[0]
queue=queue[1:]
res1=append(res1,node.Val)
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
size--
}
res2:=pingjun(res1)
res=append(res,res2)
res1=[]int{}
}
return res
}
func pingjun(res1 []int) float64{
var r float64
var value int
legth:=len(res1)
for i:=0;i<legth;i++{
value+=res1[i]
}
r=float64(value)/float64(legth)
return r
}
429. N 叉树的层序遍历
难度中等334收藏分享切换为英文接收动态反馈
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示：
- 树的高度不会超过
1000 - 树的节点总数在
[0, 10^4]之间 - 思路: 这道题依旧是模板题，只不过一个节点有多个孩子了
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func levelOrder(root *Node) [][]int {
var res [][]int
var res1 []int
var queue []*Node
if root==nil{
return res
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
for size>0{
node:=queue[0]
queue=queue[1:]
res1=append(res1,node.Val)
leght:=len(node.Children)
for i:=0;i<leght;i++{
if node.Children[i]!=nil{
queue=append(queue,node.Children[i])
}
}
size--
}
res=append(res,res1)
res1=[]int{}
}
return res
}
515. 在每个树行中找最大值
难度中等291收藏分享切换为英文接收动态反馈
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2：
输入: root = [1,2,3]
输出: [1,3]
提示：
- 二叉树的节点个数的范围是
[0,104] -231 <= Node.val <= 231 - 1- 思路：层序遍历，取每一层的最大值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) []int {
var res []int
var queue []*TreeNode
if root==nil{
return res
}
queue=append(queue,root)
tmp:=math.MinInt64
for len(queue)>0{
size:=len(queue)
for size>0{
node:=queue[0]
queue=queue[1:]
tmp=max(tmp,node.Val)
// res1=append(res1,node.Val)
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
size--
}
res=append(res,tmp)
tmp=math.MinInt64
}
return res
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
116. 填充每个节点的下一个右侧节点指针
难度中等921收藏分享切换为英文接收动态反馈
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
示例 2:
输入：root = []
输出：[]
提示：
- 树中节点的数量在
[0, 212 - 1]范围内 -1000 <= node.val <= 1000
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/
func connect(root *Node) *Node {
var tmp []*Node
var queue []*Node
if root==nil{
return root
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
for size>0{
node:=queue[0]
queue=queue[1:]
tmp=append(tmp,node)
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
size--
}
for i:=0;i<len(tmp)-1;i++{
tmp[i].Next=tmp[i+1]
}
tmp=[]*Node{}
}
return root
}
117. 填充每个节点的下一个右侧节点指针 II
难度中等663收藏分享切换为英文接收动态反馈
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
提示：
- 树中的节点数小于
6000 -100 <= node.val <= 100
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/
func connect(root *Node) *Node {
var tmp []*Node
var queue []*Node
if root==nil{
return root
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
for size>0{
node:=queue[0]
queue=queue[1:]
tmp=append(tmp,node)
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
size--
}
for i:=0;i<len(tmp)-1;i++{
tmp[i].Next=tmp[i+1]
}
tmp=[]*Node{}
}
return root
}
104. 二叉树的最大深度
难度简单1456收藏分享切换为英文接收动态反馈
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
var queue []*TreeNode
depth:=0
if root==nil{
return depth
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
depth+=1
for size>0{
node:=queue[0]
queue=queue[1:]
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
size--
}
}
return depth
}
111. 二叉树的最小深度
难度简单901收藏分享切换为英文接收动态反馈
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
var queue []*TreeNode
depth:=0
if root==nil{
return depth
}
queue=append(queue,root)
for len(queue)>0{
size:=len(queue)
depth++
for size>0{
node:=queue[0]
queue=queue[1:]
if node.Left!=nil{
queue=append(queue,node.Left)
}
if node.Right!=nil{
queue=append(queue,node.Right)
}
if node.Left==nil&& node.Right==nil{
return depth
}
size--
}
}
return depth
}