1.题目:在每个树行中找最大值
leetcode:515
这个是以空间换时间了,时间复杂度有所提高
func largestValues(root *TreeNode) []int {
res := []int{}
tmp := []int{}
if root==nil{
return res
}
lis := list.New()
lis.PushBack(root)
for lis.Len()>0{
length := lis.Len()
for i:=0;i<length;i++{
node := lis.Remove(lis.Front()).(*TreeNode)
if node.Left!=nil{
lis.PushBack(node.Left)
}
if node.Right!=nil{
lis.PushBack(node.Right)
}
tmp = append(tmp, node.Val)
}
m := max(tmp)
res = append(res, m)
tmp = []int{}
}
return res
}
func max(res []int)int{
sort.Ints(res)
var t int
if len(res)!=0{
t = res[len(res)-1]
}
return t
}
每次弹出节点的时候和最大值比较,大于则替换,
具体操作就是判断i,
如果等于0,max_val直接赋值node.val
如果i大于0说明不是第一个元素,就和max_val比较,大于则替换、
// 每次弹出节点的时候和最大值比较,大于则替换
func largestValues(root *TreeNode) []int {
res := []int{}
max_val := 0
if root==nil{
return res
}
lis := list.New()
lis.PushBack(root)
for lis.Len()>0{
length := lis.Len()
for i:=0;i<length;i++{
node := lis.Remove(lis.Front()).(*TreeNode)
if node.Left!=nil{
lis.PushBack(node.Left)
}
if node.Right!=nil{
lis.PushBack(node.Right)
}
// tmp = append(tmp, node.Val)
if i>0{
if node.Val>max_val{
max_val = node.Val
}
}else{
max_val = node.Val
}
}
res = append(res, max_val)
}
return res
}
2.题目2:填充每个节点的下一个右侧节点指针
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/
func connect(root *Node) *Node {
res := [][]*Node{}
tmp := []*Node{}
if root==nil{
return root
}
lis := list.New()
lis.PushBack(root)
for lis.Len()>0{
length := lis.Len()
for i:=0;i<length;i++{
node := lis.Remove(lis.Front()).(*Node)
if node.Left!=nil{
lis.PushBack(node.Left)
}
if node.Right!=nil{
lis.PushBack(node.Right)
}
tmp = append(tmp, node)
}
res = append(res, tmp)
tmp = []*Node{}
}
// 用来处理节点之间的关系
for i:=0;i<len(res);i++{
// j要是小于长度减一
for j:=0;j<len(res[i])-1;j++{
res[i][j].Next = res[i][j+1]
}
}
return root
}
3.遍历每个节点下的右侧节点指针
此处代码和上一题一样
4.二叉树最大深度
这道题也是套模板的题
leetcode104
func maxDepth(root *TreeNode) int {
ret := 0
if root==nil{
return 0
}
lis := list.New()
lis.PushBack(root)
for lis.Len()>0{
length := lis.Len()
for i:=0;i<length;i++{
node := lis.Remove(lis.Front()).(*TreeNode)
if node.Left!=nil{
lis.PushBack(node.Left)
}
if node.Right!=nil{
lis.PushBack(node.Right)
}
}
ret ++
}
return ret
}
5.二叉树最小深度
leetcode:111
二叉树最小深度,也是用模板,主要是什么时候他是最小深度
答:左右节点全为空
func minDepth(root *TreeNode) int {
depth := 0
if root==nil{
return 0
}
lis := list.New()
lis.PushBack(root)
for lis.Len()>0{
length := lis.Len()
for i:=0;i<length;i++{
node := lis.Remove(lis.Front()).(*TreeNode)
// 但当前节点没有左右节点的时候意味着他是最浅的
if node.Left==nil&&node.Right==nil{
return depth+1
}
if node.Left!=nil{
lis.PushBack(node.Left)
}
if node.Right!=nil{
lis.PushBack(node.Right)
}
}
depth++
}
return depth
}