首页 > 其他分享 >day13

day13

时间:2024-06-11 20:12:34浏览次数:15  
标签:node right return queue day13 root left

day13
一:层序遍历:即依据根左右继续左右依层遍历各节点

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = collections.deque([root])
        result = []
        while queue:
            level = []
            for _ in range(len(queue)):
                cur = queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            result.append(level)
        return result
"递归法"
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        levels = []
        self.helper(root,0,levels)
        return levels
    
    def helper(self,node,level,levels):
        if not node:
            return
        if len(levels) < level:
            levels.append([])
        levels[level].append(node.val)
        self.helper(node.left,level+1,levels)
        self.helper(node.right,level+1,levels)
func levelOrder(root *TreeNode) [][]int {
    arr := [][]int{}
    depth :=0
    var order func(root *TreeNode,depth int)
    order = func(root *TreeNode,depth int){
        if root == nil{
            return
        }
        if len(arr) == depth{
            arr = append(arr,[]int{})
        }
        arr[depth] = append(arr[depth],root.Val)
        order(root.Left,depth+1)
        order(root.Right,depth+1)

    }
    order(root,depth)

    return arr
}


//队列法
func levelOrder(root *TreeNode) [][]int {
    res :=[][]int {}
    if root == nil {
        return res
    }
    queue :=list.New()
    queue.PushBack(root)

    var tmpArr []int

    for queue.Len() > 0{
        length :=queue.Len()
        for i:=0;i<length;i++{
            //前弹出节点,此时为root
            node := queue.Remove(queue.Front()).(*TreeNode)
            //然后是左右
            if node.Left != nil{
                queue.PushBack(node.Left)
            }
            if node.Right != nil{
                queue.PushBack(node.Right)
            }
            //将node的值加入tmpArr中
            tmpArr = append(tmpArr,node.Val)
        }
        //再将所需结果加入res
        res = append(res,tmpArr)
        tmpArr = []int{}
    }
    return res
}

第二题层序遍历之二:
要求从叶子到根反向遍历

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        "借用dequeue将root装入"
        queue = collections.deque([root])
        result = []
        while queue:
            level = []
            "遍历途中不断将队列左弹出并将值加入level再遍历左右"
            for _ in range(len(queue)):
                cur = queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            "将level加入result里"
            result.append(level)
        "最后反转"
        return result[::-1]
//go语言原理同上
func levelOrderBottom(root *TreeNode) [][]int {
    queue := list.New()
    res := [][]int{}
    if root == nil {
        return res
    }
    queue.PushBack(root)

    for queue.Len() > 0 {
        length := queue.Len()
        tmp :=[]int{}
        for i:=0;i<length;i++{
            node := queue.Remove(queue.Front()).(*TreeNode)
            if node.Left != nil{
                queue.PushBack(node.Left)
            }
            if node.Right != nil{
                queue.PushBack(node.Right)
            }
            tmp = append(tmp,node.Val)
        }
        res = append(res,tmp)
    }
     for i:=0;i<len(res) / 2;i++ {
        res[i],res[len(res) -i -1] = res[len(res) -i -1 ],res[i]
     }
     return res
}

第三题:二叉树之右视图,即幻想在二叉树右侧观察节点

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        queue = collections.deque([root])
        right_view = []
        "先读根,再由于队列中长度即为所有节点总数,"
        while queue:
            level_size = len(queue)

            for i in range(level_size):
                node = queue.popleft()

                if i == level_size - 1:
                    right_view.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return right_view
func rightSideView(root *TreeNode) []int {

    if root == nil {
        return nil
    }
    //先层序遍历再取每层最后一个元素即最右边的
    res := make([]int,0)
    queue := list.New()
    queue.PushBack(root)

    for queue.Len() > 0{
        length := queue.Len()
        for i:=0;i<length;i++{
            node := queue.Remove(queue.Front()).(*TreeNode)
            if node.Left != nil{
                queue.PushBack(node.Left)
            }
            if node.Right != nil{
                queue.PushBack(node.Right)
            }
            if i == length - 1 {
                res = append(res,node.Val)
            }
        }
    }
    return res
}

第四题:
求二叉树每层的平均值
原理实际上是层序遍历时每次求和求平均值

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        queue = collections.deque([root])
        averages = []

        while queue:
            size = len(queue)
            level_sum = 0

            for i in range(size):
                node = queue.popleft()

                level_sum += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            averages.append(level_sum / size)
        return averages
func averageOfLevels(root *TreeNode) []float64 {
    if root == nil {
        return nil
    }
    res := make([]float64,0)
    queue := list.New()
    queue.PushBack(root)

    var sum int
    for queue.Len() > 0{
        length := queue.Len()
        for i:=0;i<length;i++{
            node := queue.Remove(queue.Front()).(*TreeNode)
            if node.Left != nil{
                queue.PushBack(node.Left)
            }
            if node.Right != nil{
                queue.PushBack(node.Right)
            }
            sum += node.Val
        }
        res = append(res,float64(sum) / float64(length))
        //每层需要被清空
        sum = 0
    }
    return res
}

第五题:N叉树的层序遍历

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
        result = []
        queue = collections.deque([root])

        while queue:
            level_size = len(queue)
            level = []

            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                "遍历孩子并不断将其加入queue中,使得上层循环中不断访问节点值并最终得到结果集"
                for child in node.children:
                    queue.append(child)
            result.append(level)
        return result    
"递归法不是很熟悉"
class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: 
            return []
            result = []
            def travelsal(root,depth):
                if len(result) == depth:
                    result.append([])
                result[depth].append(root.val)
                if root.children:
                    for i in range(len(root.children)):
                        travelsal(root.children[i],depth+1)
            travelsal(root,0)
            return result        
func levelOrder(root *Node) [][]int {
    queue := list.New()
    res := [][]int{}
    if root == nil {
        return res
    }
    queue.PushBack(root)
    for queue.Len() > 0{
        length := queue.Len()
        var tmp []int
        for T :=0;T < length;T++{
            myNode := queue.Remove(queue.Front()).(*Node)
            tmp = append(tmp,myNode.Val)
            for i:=0;i<len(myNode.Children);i++{
                queue.PushBack(myNode.Children[i])
            }
        }
        res = append(res,tmp)
    }
    return res
}

题目六:在每个二叉树行中找最大值

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        queue = collections.deque([root])

        while queue:
            level_size = len(queue)
            max_val = float('-inf')

            for _ in range(level_size):
                node = queue.popleft()
                max_val = max(max_val,node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(max_val)
        return result
func largestValues(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    queue := list.New()
    queue.PushBack(root)
    ans := make([]int,0)
    temp := math.MinInt64

    for queue.Len() >0{
        length := queue.Len()
        for i:=0;i<length;i++{
            node := queue.Remove(queue.Front()).(*TreeNode)
            temp = max(temp,node.Val)
            if node.Left != nil{
                queue.PushBack(node.Left)
            }
            if node.Right != nil {
                queue.PushBack(node.Right)
            }
        }
        ans = append(ans,temp)
        temp = math.MinInt64
    }
    return ans
}
func max(x,y int) int {
    if x >  y{
        return x
    }
    return y
}

题目七 侧节点指针的填充
给定一个完美二叉树每个节点都有两个字节点


class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root
        
        queue = collections.deque([root])
        
        while queue:
            level_size = len(queue)
            prev = None

            for i in range(level_size):
                node = queue.popleft()

                if prev:
                    prev.next = node
                
                prev = node
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return root
func connect(root *Node) *Node {
    if root == nil {
        return root
    }	
    queue := list.New()
    queue.PushBack(root)
    tempArr :=make([]*Node,0)
    for queue.Len() > 0{
        length := queue.Len()
        for i:=0;i<length;i++{
            node := queue.Remove(queue.Front()).(*Node)
            if node.Left != nil{
                queue.PushBack(node.Left)
            }
            if node.Right != nil{
                queue.PushBack(node.Right)
            }
            tempArr = append(tempArr,node)
        }
        if len(tempArr) > 1 {
            for i:=0;i<len(tempArr)-1;i++{
                tempArr[i].Next = tempArr[i+1]
            }
        }
        tempArr = []*Node{}
    }
    return root
}

题目八与上题本质上没区别

题目九:反转二叉树

"遍历法,前中后序遍历交换指针即可"
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left,root.left = root.right,root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
"广度优先遍历,并交换指针"
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        queue = collections.deque([root])
        while queue:
            for i in range(len(queue)):
                node = queue.popleft()
                node.left,node.right = node.right,node.left
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return root
//前序的递归
func invertTree(root *TreeNode) *TreeNode {
    if root  == nil{
        return nil
    }
    root.Left,root.Right = root.Right,root.Left
    invertTree(root.Left)
    invertTree(root.Right)

    return root
}
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    queue := list.New()
    node := root
    queue.PushBack(node)
    for queue.Len() > 0{
        length := queue.Len()
        for i:=0;i<length;i++{
            e := queue.Remove(queue.Front()).(*TreeNode)
            e.Left,e.Right = e.Right,e.Left
            if e.Left != nil {
                queue.PushBack(e.Left)
            }
            if e.Right != nil{
                queue.PushBack(e.Right)
            }
        }
    }
    return root
}

题目十:判断二叉树是否对称

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.compare(root.left,root.right)
    def compare(self,left,right):
        if left == None and right != None:
            return False
        elif left != None and right == None:
            return False
        elif left == None and right== None:
            return True
        elif left.val != right.val:
            return False
        
        outside = self.compare(left.left,right.right)
        inside = self.compare(left.right,right.left)
        isSame = outside and inside
        return isSame
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        queue = collections.deque([root.left,root.right])
        while queue:
            level_size = len(queue)
            if level_size % 2 != 0:
                return False
            level_vals = []
            for i in range(level_size):
                node = queue.popleft()
                if node:
                    level_vals.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
                else:
                    level_vals.append(None)
            if level_vals != level_vals[::-1]:
                return False
        return True
func defs(left *TreeNode,right *TreeNode)bool {
    if left == nil && right == nil {
        return true
    }
    if left == nil || right == nil {
        return false
    }
    if left.Val != right.Val{
        return false
    }
    return defs(left.Left,right.Right) && defs(right.Left,left.Right)
}
func isSymmetric(root *TreeNode) bool {
    return defs(root.Left,root.Right)
}
func isSymmetric(root *TreeNode) bool {
    var queue []*TreeNode
    if root != nil {
        queue = append(queue,root.Left,root.Right)
    }
    for len(queue) > 0{
        left :=queue[0]
        right :=queue[1]
        queue = queue[2:]
        if left == nil && right == nil{
            continue
        }
        if left == nil || right == nil || left.Val != right.Val{
            return false
        }
        queue = append(queue,left.Left,right.Right,right.Left,left.Right)
    }
    return true
}

标签:node,right,return,queue,day13,root,left
From: https://www.cnblogs.com/leisure535/p/18242638

相关文章

  • 代码随想录算法训练营day13(栈与队列)
    代码随想录算法训练营day:学习内容:今天主要学习队列239347学习产出:239一开始想着直接暴力遍历,但是时间复杂度为nk。采用deque实现一个单调队列,因为我们需要一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最......
  • day13——常用API&日期类
    day13——常用API&日期类一、StringBuilder类StringBuilder代表可变字符串对象,相当于是一个容器,它里面的字符串是可以改变的,就是用来操作字符串的。好处:StringBuilder比String更合适做字符串的修改操作,效率更高,代码也更加简洁。1.1StringBuilder方法演示接下来我们用......
  • 今日刷三题(day13):ISBN号码+kotori和迷宫+矩阵最长递增路径
    题目一:ISBN号码题目描述:每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符,其规定格式如“x-xxx-xxxxx-x”,其中符号“-”是分隔符(键盘上的减号),最后一位是识别码,例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语......
  • m1_day13
    课程内容:Object类的核心方法集合框架集合之ArrayList集合Object类的核心方法:Object是Java中的鼻祖类所有类的直接父类/间接父类toString():制定一个对象打印显示的内容任何一个引用数据类型都默认继承Object类获得toString()方法在Object类中toString()......
  • JAVA语言学习-Day13
    参考教学视频:秦疆JVM概述JVM位置:操作系统之上JVM的体系结构.java->ClassFile->类加载器Classloader<-->运行时数据区RuntimeDataArea<-->本地方法接口<-本地方法库运行时数据区RuntimeDataArea<-->执行引擎方法区:MethodAreaJava栈:Stack本地方......
  • day13- 模块和包
    这节我们学习模块和包,这块呢,我们在实际使用的过程中,首先保证自己会用就可以,其次也可以加深对Python代码的理解。1、什么是模块开始之前,那我们思考下,之前学的过变量,函数属于一个模块吗?模块呢,就是Python程序,简单来说,就是一个.py的文件,就是属于一个模块那说明我们之前的函数和变......
  • day13-阶段总结
    1.知识补充1.1nolocal关键字在之前的课程中,我们学过global关键字。name='root'defouter():name="武沛齐"definner():globalnamename=123inner()print(name) #武沛齐outer()print(name) #123其实,还有一个nolocal......
  • 代码随想录算法训练营Day13|239滑动窗口最大值 347前k个高频元素
    学习了Carl的视频今日任务 239. 滑动窗口最大值 (一刷至少需要理解思路)之前讲的都是栈的应用,这次该是队列的应用了。本题算比较有难度的,需要自己去构造单调队列,建议先看视频来理解。 题目链接/文章讲解/视频讲解:代码随想录 347.前 K 个高频元素 (一刷至少需要理......
  • 【蓝桥杯备赛】Day13:贪心算法(倒计时30天)
    题目1:题目3040:AnEasyProblem给定一个正整数N,求最小的、比N大的正整数M,使得M与N的二进制表示中有相同数目的1。举个例子,假如给定的N为78,其二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。输入格......
  • 代码随想录算法训练营day13 | leetcode 239. 滑动窗口最大值、347. 前 K 个高频元素
    目录题目链接:239.滑动窗口最大值-困难题目链接:347.前K个高频元素-中等题目链接:239.滑动窗口最大值-困难题目描述:给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。......