做网站大家都找谁,公司网站改版需要怎么做,wordpress折叠菜单插件,wordpress开发文档二叉树相关推荐 107.二叉树的层次遍历II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II总结 107.二叉树的层次遍历II
切片本质是一个结构体#xff0c;包含… 二叉树相关推荐 107.二叉树的层次遍历II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II总结 107.二叉树的层次遍历II
切片本质是一个结构体包含一个指向底层数组的指针(prt)长度len容量cap。如果通过函数对切片进行赋值修改会传递到函数外但如果在函数内对切片进行扩容会产生新的底层数组但数组外的切片仍指向原来的旧切片进而导致对切片的修改无法传递到函数外 (1)递归
func levelOrderBottom(root *TreeNode) [][]int {res : [][]int{}var help func(root *TreeNode, depth int) help func(root *TreeNode, depth int) {if root nil {return}if depth len(res) {res append(res, []int{})}res[depth] append(res[depth], root.Val)depthhelp(root.Left, depth)help(root.Right, depth)} help(root, 0)for i, j : 0, len(res) - 1; i j; i, j i 1, j - 1 {res[i], res[j] res[j], res[i]}return res
}
(2)层序
func levelOrderBottom(root *TreeNode) [][]int {res : [][]int{}if root nil {return res}node : rootqueue : []*TreeNode{root}for len(queue) 0 {size : len(queue)vals : []int{}for i : 0; i size; i {node queue[0]queue queue[1:]vals append(vals, node.Val)if node.Left ! nil {queue append(queue, node.Left)}if node.Right ! nil {queue append(queue, node.Right)}}// 反向插入结果res append(res, []int{})copy(res[1:], res[0:])res[0] vals}return res
}199.二叉树的右视图
(1)递归 中—右—左顺序访问保证了每层最先访问的是最右边节点 如果当前节点的高度等于len(res)将其值加入res。当前节点类似于为res扩张探路。
func rightSideView(root *TreeNode) []int {res : []int{}var help func(root *TreeNode, depth int)help func(root *TreeNode, depth int) {if root nil {return}if depth len(res) {res append(res, root.Val)}depthhelp(root.Right, depth)help(root.Left, depth)}help(root, 0)return res
}(2)层序
func rightSideView(root *TreeNode) []int {res : []int{}if root nil {return res}curQueue : []*TreeNode{root}for len(curQueue) 0 {nextQueue : []*TreeNode{}size : len(curQueue)for i : 0; i size; i {node : curQueue[i]if node.Left ! nil {nextQueue append(nextQueue, node.Left)}if node.Right ! nil {nextQueue append(nextQueue, node.Right)}if i size - 1 {res append(res, node.Val)}}curQueue nextQueue}return res
}637.二叉树的层平均值
(1)递归 创建结构体nodeGroup存储当前层node个数和sum 类似上题解法若当前节点高度小于len(nodeGroup)对当前层nodeGroup的count和sum进行更新【count1,sumroot.val】若当前节点高度等于len(nodeGroup)创建新的层并对count和sum赋值【count1,sumroot.val】。
type nodeGroup struct {Count intsum int
}func averageOfLevels(root *TreeNode) []float64 {res : []float64{}resGroup : []nodeGroup{{0, 0}}var help func(root *TreeNode, depth int)help func(root *TreeNode, depth int) {if root nil {return}if depth len(resGroup) {resGroup[depth].CountresGroup[depth].sum root.Val} else {resGroup append(resGroup, nodeGroup{1, root.Val})}depthhelp(root.Left, depth)help(root.Right, depth)}help(root, 0)for _, countSum : range resGroup {avg : float64(countSum.sum) / float64(countSum.Count)res append(res, avg)}return res
}(2)层序
func averageOfLevels(root *TreeNode) []float64 {res : []float64{}curQueue : []*TreeNode{root}for len(curQueue) 0 {size : len(curQueue)sum : 0nextQueue : []*TreeNode{}for _, node : range curQueue {sum node.Valif node.Left ! nil {nextQueue append(nextQueue, node.Left)}if node.Right ! nil {nextQueue append(nextQueue, node.Right)}}res append(res, float64(sum)/float64(size))curQueue nextQueue}return res
}429.N叉树的层序遍历
(1)递归追加当前层数据如果当前节点高度等于len(res)创建新层。
func levelOrder(root *Node) [][]int {res : [][]int{}var help func(root *Node, depth int)help func(root *Node, depth int) {if root nil {return }if depth len(res) {res append(res, []int{})}res[depth] append(res[depth], root.Val)depthfor _, child : range root.Children {help(child, depth)}}help(root, 0)return res
}(2)迭代创建新层追加数据。
func levelOrder(root *Node) [][]int {res : [][]int{}if root nil {return res}curQueue : []*Node{root}depth : 0for len(curQueue) 0 {nextQueue : []*Node{}res append(res, []int{})for _, node : range curQueue {res[depth] append(res[depth], node.Val)for _, child : range node.Children {nextQueue append(nextQueue, child)}}depthcurQueue nextQueue}return res
}515.在每个树行中找最大值
(1)递归
func largestValues(root *TreeNode) []int {res : []int{}var help func(root *TreeNode, depth int) help func(root *TreeNode, depth int) {if root nil {return}if depth len(res) {res append(res, root.Val)}if root.Val res[depth] {res[depth] root.Val}depthhelp(root.Left, depth)help(root.Right,depth)return}help(root, 0)return res
}(2)迭代
func largestValues(root *TreeNode) []int {res : []int{}if root nil {return res}depth : 0curQueue : []*TreeNode{root}for len(curQueue) 0 {nextQueue : []*TreeNode{}for _, node : range curQueue {if depth len(res) {res append(res, node.Val)}if node.Val res[depth] {res[depth] node.Val}if node.Left ! nil {nextQueue append(nextQueue, node.Left)}if node.Right ! nil {nextQueue append(nextQueue, node.Right)}}depthcurQueue nextQueue}return res
}116.填充每个节点的下一个右侧节点指针
(1)递归如果当前节点高度等于len(res)证明该节点是最新一层最左侧节点将其追加到res中否则将res[depth]节点指向当前节点并更新res[depth]为当前节点
func connect(root *Node) *Node {res : []*Node{}var help func(root *Node, depth int) help func (root *Node, depth int) {if root nil {return}if depth len(res) {res append(res, root)} else {res[depth].Next rootres[depth] root}depthhelp(root.Left, depth)help(root.Right, depth)}help(root, 0)return root
}(2)迭代
func connect(root *Node) *Node {if root nil {return root}curQueue : []*Node{root}for len(curQueue) 0 {nextQueue : []*Node{}size : len(curQueue)for i : 0; i size; i {node : curQueue[i]if node.Left ! nil {nextQueue append(nextQueue, node.Left)}if node.Right ! nil {nextQueue append(nextQueue, node.Right)}if i size - 1 {break}node.Next curQueue[i 1]}curQueue nextQueue}return root
}117.填充每个节点的下一个右侧节点指针II
题解只能说与上题一模一样
总结
树递归层序迭代一个套路走完所有题 大佬递归方法太秀了必须码住
