专栏首页Bingo的深度学习杂货店Leetcode【429、559、589、590、669】

Leetcode【429、559、589、590、669】

问题描述:【Tree】429. N-ary Tree Level Order Traversal
解题思路:

这道题是给一棵 N 叉树,层次遍历将每一层的结点保存在列表中。

层次遍历就是使用队列,将每一层的地址和层数保存在队列中即可。

Python3 实现:
"""
# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return None
        q, ans = collections.deque(), []
        q.append((root, 1))
        deep = 1
        while q:  # 队列不为空,一直遍历到为空
            ans.append([])
            while q and q[0][1] == deep: # 相同层
                addr = q.popleft()[0]  # 取该层根结点地址
                ans[-1].append(addr.val)
                for child in addr.children:  # 将根结点的孩子放入队列
                    q.append((child, deep + 1))
            deep += 1  # 层数加1
        return ans

问题描述:【Tree】559. Maximum Depth of N-ary Tree
解题思路:

这道题是给一个 N 叉树,求最大深度。

二叉树的最大深度为 max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1拓展到 N 叉树,只需要对于 root.children 的每一个孩子 child (for child in root.children),更新最大深度 ans = max(ans, self.maxDepth(child)),最后 ans + 1 就是答案。

Python3 实现:
"""
# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        ans = 0  # 最大深度
        if not root:
            return 0
        for child in root.children:
            ans = max(ans, self.maxDepth(child))
        return ans + 1

问题描述:【Tree】589. N-ary Tree Preorder Traversal
解题思路:

这道题是给一个 N 叉树,将前序遍历的结果保存在列表中。

前序遍历:先保存根,再递归孩子 child(for child in root.children)。

Python3 实现:
"""
# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children  # root.children 是以列表的形式存储的
"""
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        self.ans = []   # 比将 ans 作为参数传入的效率高一些
        self.dfs(root)
        return self.ans
    
    def dfs(self, root):
        if root:
            self.ans.append(root.val)
            for child in root.children:  # root.children 是以列表的形式存储的
                self.dfs(child)

问题描述:【Tree】590. N-ary Tree Postorder Traversal
解题思路:

这道题是给一个 N 叉树,将后序遍历的结果保存在列表中。

思路同上面的 Leetcode 589。后序遍历:先递归孩子 child(for child in root.children),再保存根。

Ptthon3 实现:
"""
# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children  # root.children 是以列表的形式存储的
"""
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        self.ans = []   # 比将 ans 作为参数传入的效率高一些
        self.dfs(root)
        return self.ans
    
    def dfs(self, root):
        if not root:
            return
        for child in root.children:  # root.children 是以列表的形式存储的
            self.dfs(child)
        self.ans.append(root.val)

问题描述:【Tree】669. Trim a Binary Search Tree
解题思路:

这道题是给一棵二叉搜索树和一个区间 [L,R],通过修剪这棵树,使得所有结点的值在 [L,R] 中 (R>=L) 。

  • 当 root 的值位于 L 和 R 之间,则递归修剪其左右子树,返回 root。
  • 当 root 的值小于 L,则其左子树的值都小于 L,抛弃左子树,返回修剪过的右子树。
  • 当 root 的值大于 R,则其右子树的值都大于 R,抛弃右子树,返回修剪过的左子树。

递归的思想就在于我们不用管递归内部怎么实现的,我们只需要知道递归函数可以完成某种操作,递归真正需要关注的是递归的出口和返回值。因此这道题我们可以想象 self.trimBST(root.right, L, R) 就能修建完右子树并返回修剪好的根结点,同理 self.trimBST(root.left, L, R) 就能修建完左子树并返回修剪好的根结点。

Python3 实现:
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
        if not root:
            return None
        if root.val < L:  # 抛弃左子树,返回修剪过的右子树
            return self.trimBST(root.right, L, R)
        if root.val > R:  # 抛弃右子树,返回修剪过的左子树
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • N叉树问题-LeetCode 429、589、590、105、106(构建二叉树,N叉树遍历)

    给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。 例如,给定一个 3叉树 :

    算法工程师之路
  • SUMO学习笔记(1)

    https://sumo.dlr.de/docs/Tutorials/Hello_World.html

    嘘、小点声
  • 各种类型文件的Content-Type 原

     17      '.123': 'application/vnd.lotus-1-2-3',   18      '.3ds': 'image/x-3ds'...

    晓歌
  • Python爬虫有用的库:fake_useragent

    练习爬虫的很多小伙伴,在进行request请求时,大部分情况下都要添加一个请求头,而最常见的就是添加user-agent,帮助爬虫伪装成浏览器正常操作。

    远方的星
  • 如何根据日志查看删除的数据(转译)

    原文地址:https://raresql.com/2011/10/22/how-to-recover-deleted-data-from-sql-sever/ ...

    用户1217611
  • 1000个常用的Python库和示例代码

    下面是programcreek通过分析大量开源代码,提取出的最常用的python库。

    用户4962466
  • Protocol Buffer序列化对比Java序列化.

    初识 Protocol Buff是谷歌推出的一种序列化协议. 而Java序列化协议也是一种协议. 两者的目的是, 将对象序列化成字节数组, 或者说是二进制数据,...

    用户1216491
  • java开发_java小程序_邮死你(yousini)_源码下载

    ==========================================================

    Hongten
  • (七十一)c#Winform自定义控件-折线图

    GitHub:https://github.com/kwwwvagaa/NetWinformControl

    冰封一夏
  • 5分钟理解编译系统

      本文以一个C语言版的hello world例子阐述编译系统四个阶段的工作内容。源程序hello.c如下:

    用户1432189
  • 四级地址插件升级改造(京东商城地址选择插件)city-picker

    最近公司做的项目要和京东的数据做对接,所以要做个类似京东商品的详情页。页面的数据,是可以从京东接口获取到的,但是地址插件选择的效果需要自己实现。前端的同事在之前...

    纪莫
  • 二叉树:层序遍历登场!

    给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。

    代码随想录
  • 温湿度系统(花葵、库房检测)

    用户1112962
  • (八十九)c#Winform自定义控件-自定义滚动条(treeview、panel、datagridview、listbox、listview、textbox)

    GitHub:https://github.com/kwwwvagaa/NetWinformControl

    冰封一夏
  • (二十九)c#Winform自定义控件-文本框(二)

    GitHub:https://github.com/kwwwvagaa/NetWinformControl

    冰封一夏
  • 可输出sql的PrepareStatement封装

    WindWant
  • 本周小结!(二叉树)

    发现大家周末的时候貌似都不在学习状态,周末的文章浏览量和打卡情况照工作日差很多呀,可能是本周日是工作日了,周六得好好放松放松,哈哈,理解理解,但我还不能不更啊,...

    代码随想录
  • 001 红黑树(二)之 C语言的实现(2)

    文章来源: http://www.cnblogs.com/skywang12345/p/3624177.html

    范蠡
  • java开发_闹钟

    ==========================================================

    Hongten

扫码关注云+社区

领取腾讯云代金券