您好,登录后才能下订单哦!
本篇文章给大家分享的是有关如何理解二叉树的层次遍历,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。
算法:
树的层次遍历是树的基本操作之一,包括二叉树的层次遍历,多叉树的层次遍历,以及二叉树层次遍历的变形题目,层次遍历+每一层的节点的翻转等操作。
对于这类题目,典型算法就是先将树按照层次存入数组当中,然后统一对每一层的数据进行数据处理。
题目1:
代码实现:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/*
方法1:非递归操作
*/
/*
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
var stack []*TreeNode
var result [][]int
stack = append(stack,root)
for {
if len(stack) == 0 {
break;
}
res,stack1 := helper(stack)
if len(res) != 0 {
result = append(result,res)
}
stack = stack1
}
return result
}
func helper(stack []*TreeNode)(res []int, stackRes []*TreeNode){
if len(stack) == 0{
return
}
for i:=0;i<len(stack); i++{
node := stack[i]
if node == nil {
continue
}
res = append(res,node.Val)
stackRes = append(stackRes,node.Left)
stackRes = append(stackRes,node.Right)
}
return
}
*/
/*
解法:队列来操作,
树的层次遍历,从左到右遍历树的每一层存入对应的数组即可
*/
/*
方法2:递归操作
利用二叉树的先序遍历方法,也就是先访问根节点,在访问做左孩子,然后访问右孩子。
*/
func levelOrder(root *TreeNode) [][]int {
return preOrder(root, 0, [][]int{})
}
func preOrder(root *TreeNode, level int, res [][]int) [][]int {
if root == nil {
return res
}
// 1.根节点的处理
// 这里因为level从0开始计算的缘故,len放进去值之后就是1,所以==的时候,便是是新的一层开始
if level == len(res) {
res = append(res,[]int{root.Val})
} else {
res[level] = append(res[level],root.Val)
}
// 2.左孩子节点的处理
res = preOrder(root.Left,level+1,res)
// 3.右孩子节点的处理
res = preOrder(root.Right,level+1,res)
return res
}
执行结果:
题目2:
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
代码实现:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrderBottom(root *TreeNode) [][]int {
r := [][]int{}
order(root,0,&r)
for i,j:= 0, len(r)-1;i<j;{
r[i],r[j] = r[j],r[i]
i++
j--
}
return r
}
func order(root *TreeNode,level int,res *[][]int) {
if root == nil {
return
}
if len(*res)-1 < level {
*res = append(*res,[]int{root.Val})
} else {
(*res)[level] = append((*res)[level],root.Val)
}
order(root.Left,level+1,res)
order(root.Right,level+1,res)
return
}
执行结果:
题目3:
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
代码实现:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
res := [][]int{}
levelOrder(root,0, &res)
for i:=0; i< len(res); i++ {
if i%2 == 1{
j,k:=0,len(res[i])-1
for j < k{
res[i][j],res[i][k] = res[i][k],res[i][j]
j++
k--
}
}
}
return res
}
func levelOrder(root *TreeNode, l int, res *[][]int) {
if root == nil {
return
}
if len(*res)-1 < l {
*res = append(*res,[]int{root.Val})
} else {
(*res)[l] = append((*res)[l],root.Val)
}
levelOrder(root.Left,l+1,res)
levelOrder(root.Right,l+1,res)
return
}
// 需要: 先按照层次去遍历存储,然后统一的做整理,调整需要转换的对应层次
结果输出:
题目4.
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
代码实现:
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func levelOrder(root *Node) [][]int {
if root == nil {
return nil
}
res := [][]int{}
levelOrderOk(root,0,&res)
return res
}
func levelOrderOk(root *Node,l int, res *[][]int){
if len(*res)-1 < l {
*res = append(*res,[]int{root.Val})
} else {
(*res)[l] = append((*res)[l],root.Val)
}
for _,t := range root.Children {
levelOrderOk(t,l+1,res)
}
return
}
执行结果:
以上就是如何理解二叉树的层次遍历,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。