当前位置：首页 > article >正文

力扣刷题第二十六天--二叉树

article 2024/12/26 20:25:20

前言

昨天看总决赛，差距太大，看的没意思，真的是一点变通没有啊。难受，没有写题的状态了。大概率是最后一次看比赛了，青春已复过，白日忽相催。召唤师要和生活对线了。英雄们的语音，台词，技能历历在目，再多不舍，也要说再见。Legends never die！调整状态，再出发！再高的山，再长的河，也会越过！

层序遍历的模板基本上就是这样，掌握好。

内容

一、二叉树的层序遍历

102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

本题为后端高频面试题，被收录于《热招技术岗上岸指南》

广度优先搜素

层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 //用切片模拟队列
func levelOrder(root *TreeNode) [][]int {
   var  res [][]int
   if root==nil{
       return res
   }
   curLevel:=[]*TreeNode{root}// 存放当前层节点
   for len(curLevel)>0{
       nextLevel:=[]*TreeNode{}// 准备通过当前层生成下一层
       vals:=[]int{}

       for _,node:=range curLevel{
           vals=append(vals,node.Val)// 收集当前层的值
           if node.Left!=nil{ // 收集下一层的节点
               nextLevel=append(nextLevel,node.Left)
           }
           if node.Right!=nil{
               nextLevel=append(nextLevel,node.Right)
           }
       }
       res=append(res,vals)
       curLevel=nextLevel// 将下一层变成当前层
   }
   return res
}

二、二叉树的层序遍历II

107.二叉树的层序遍历II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

广度优先搜素

上一题反转一下结果集即可

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
     var res [][]int
     if root==nil{
         return res
     }
     curLevel:=[]*TreeNode{root}
     for len(curLevel)>0{
         nextLevel:=[]*TreeNode{}
         vals:=[]int{}
         for _,node:=range curLevel{
             vals=append(vals,node.Val)
             if node.Left!=nil{
                 nextLevel=append(nextLevel,node.Left)
             }
             if node.Right!=nil{
                 nextLevel=append(nextLevel,node.Right)
             }
         }
         res=append(res,vals)
        curLevel=nextLevel
     }
     n:=len(res)
     for i:=0;i<n/2;i++{
         res[i],res[n-1-i]=res[n-1-i],res[i]
     }
     return res
}