四川盐亭网站制作公司

如何理解二叉树的层次遍历

本篇文章给大家分享的是有关如何理解二叉树的层次遍历，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

创新互联公司自2013年起，是专业互联网技术服务公司，拥有项目网站制作、成都做网站网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元奎屯做网站,已为上家服务,为奎屯各地企业和个人服务,联系电话:18982081108

算法：

树的层次遍历是树的基本操作之一，包括二叉树的层次遍历，多叉树的层次遍历，以及二叉树层次遍历的变形题目，层次遍历+每一层的节点的翻转等操作。

对于这类题目，典型算法就是先将树按照层次存入数组当中，然后统一对每一层的数据进行数据处理。

题目1:

102. 二叉树的层序遍历

如何理解二叉树的层次遍历

代码实现：

/** * 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        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        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 }

执行结果：

如何理解二叉树的层次遍历

以上就是如何理解二叉树的层次遍历，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注创新互联行业资讯频道。


网站标题：如何理解二叉树的层次遍历
文章转载：http://scyanting.com/article/gjjopo.html

其他资讯