专栏首页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 条评论
登录 后参与评论

相关文章

  • 剑指offer【50~59】

    排序数组,很明显二分查找,找到第一个 >= k 的元素索引以及第一个 > k 的元素索引,两者相减即为答案,即 lowerBound - upperBound。...

    echobingo
  • 剑指offer【60~68】

    动态规划。令 dp[n][6*n],其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。则 dp[-1][1...6*n] 就是每一种点数的次数。点...

    echobingo
  • 剑指offer【30~39】

    除了存储数据的栈 stack,再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步,只不过其是一个递减栈。如 stack = [...

    echobingo
  • python收发邮件客户端

    程序员不务正业
  • 接口自动化框架pyface详细介绍

    本框架系本人结合一些实践经验和开源框架设计思想,在家基于兴趣爱好独立完成的代码开发。

    测试老树
  • Python3 TKinter Plac

    py3study
  • pygame系列_箭刺Elephant游戏_源码下载

    http://www.pygame.org/docs/tut/chimp/ChimpLineByLine.html

    Hongten
  • TensorFlow-VGG16模型复现

    VGG全称是指牛津大学的Oxford Visual Geometry Group,该小组在2014年的ImageNet挑战赛中,设计的VGG神经网络模型在定位和...

    xxpcb
  • python 使用pymssql连接sq

    ----原文地址:http://www.cnblogs.com/baiyangcao/p/pymssql_basic.html

    py3study
  • ​Python 之父的解析器系列之三:生成一个 PEG 解析器

    声明 | 本翻译是出于交流学习的目的,基于 CC BY-NC-SA 4.0 授权协议。为便于阅读,内容略有改动。

    Python猫

扫码关注云+社区

领取腾讯云代金券