如何理解二叉樹的層次遍歷
本篇文章給大家分享的是有關(guān)如何理解二叉樹的層次遍歷，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
創(chuàng)新互聯(lián)公司自2013年起，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站制作、成都做網(wǎng)站網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元奎屯做網(wǎng)站,已為上家服務(wù),為奎屯各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108
算法：
樹的層次遍歷是樹的基本操作之一，包括二叉樹的層次遍歷，多叉樹的層次遍歷，以及二叉樹層次遍歷的變形題目，層次遍歷+每一層的節(jié)點(diǎn)的翻轉(zhuǎn)等操作。
對(duì)于這類題目，典型算法就是先將樹按照層次存入數(shù)組當(dāng)中，然后統(tǒng)一對(duì)每一層的數(shù)據(jù)進(jìn)行數(shù)據(jù)處理。
題目1:
102. 二叉樹的層序遍歷
代碼實(shí)現(xiàn)：
/*** 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 []*TreeNodevar result [][]intstack = 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}*//*解法：隊(duì)列來操作，樹的層次遍歷，從左到右遍歷樹的每一層存入對(duì)應(yīng)的數(shù)組即可*//*方法2:遞歸操作利用二叉樹的先序遍歷方法，也就是先訪問根節(jié)點(diǎn)，在訪問做左孩子，然后訪問右孩子。*/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.根節(jié)點(diǎn)的處理// 這里因?yàn)閘evel從0開始計(jì)算的緣故，len放進(jìn)去值之后就是1，所以==的時(shí)候，便是是新的一層開始if level == len(res) {res = append(res,[]int{root.Val})} else {res[level] = append(res[level],root.Val)}// 2.左孩子節(jié)點(diǎn)的處理res = preOrder(root.Left,level+1,res)// 3.右孩子節(jié)點(diǎn)的處理res = preOrder(root.Right,level+1,res)return res}
執(zhí)行結(jié)果：
題目2:
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
代碼實(shí)現(xiàn)：
/*** 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}
執(zhí)行結(jié)果：
題目3:
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
代碼實(shí)現(xiàn)：
/*** 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])-1for 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}// 需要: 先按照層次去遍歷存儲(chǔ)，然后統(tǒng)一的做整理，調(diào)整需要轉(zhuǎn)換的對(duì)應(yīng)層次
結(jié)果輸出：
題目4.
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
代碼實(shí)現(xiàn)：
/*** 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}
執(zhí)行結(jié)果：
以上就是如何理解二叉樹的層次遍歷，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見到或用到的。希望你能通過這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
本文題目：如何理解二叉樹的層次遍歷
標(biāo)題來源：http://aaarwkj.com/article30/gjjopo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、網(wǎng)站設(shè)計(jì)公司、網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、營銷型網(wǎng)站建設(shè)、電子商務(wù)
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
