专栏首页Bingo的深度学习杂货店Leetcode【700、872、897、965、1022】

Leetcode【700、872、897、965、1022】

问题描述:【Tree】700. Search in a Binary Search Tree
解题思路:

这道题是给一棵二叉搜索树(BST),查找给定的结点。结点不存在返回 NULL。

利用 BST 的特点,进行二分查找即可。

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 searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return None
        if root.val == val:
            return root
        elif root.val > val:
            return self.searchBST(root.left, val)
        elif root.val < val:
            return self.searchBST(root.right, val)

问题描述:【Tree】872. Leaf-Similar Trees
解题思路:

这道题是给两棵树,判断它们的叶子序列(从左到右)是否相同。

将两棵树的叶子序列保存在 list 中,判断二者是否相同即可。

1、判断叶子的条件是 root.left == None and root.right == None,返回 [root.val]; 2、还要注意单子树的情况([1, 2] 或 [1, null, 2]),应该返回 [];

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 leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def leafSeq(root):  # 得到树的叶子序列
            if not root:  # 防止单子树(如 [1,2] 或者 [1,null,2])
                return []
            if root.left == None and root.right == None:  # 叶子
                return [root.val]
            return leafSeq(root.left) + leafSeq(root.right)
        
        return leafSeq(root1) == leafSeq(root2)

问题描述:【Tree】897. Increasing Order Search Tree
解题思路:

这道题是给一棵二叉搜索树,将结点按照从小到大重新排列,构造一棵只有右结点的树。

先前序遍历将每个结点保存在 list 中,再构造只有右结点的树。构造右结点的树时,除了根结点 node 外,还要有一个工作指针 cur,在遍历 list 的过程中,cur 每次往右子树走(cur = cur.right),最后返回 node 即可。

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 increasingBST(self, root: TreeNode) -> TreeNode:
        
        def in_order(root):  # 中序遍历,保存结点
            if not root:
                return []
            return in_order(root.left) + [TreeNode(root.val)] + in_order(root.right)
        
        nodelist = in_order(root)
        node = cur = nodelist[0]  # node:指向根结点,cur:往右子树走
        for i in range(1, len(nodelist)):
            cur.right = nodelist[i]
            cur = cur.right
        return node

问题描述:【Tree】965. Univalued Binary Tree
解题思路:

这道题是给一棵二叉树,判断其是否是单值二叉树(所有结点值都相同)。

1、先将根结点的值作为目标值 tar,将 tar 也参与递归函数; 2、如果 root 为 None,返回 True; 3、如果 root.val == tar,就递归左右子树,返回左右子树的判断结果; 4、否则返回 False。

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 isUnivalTree(self, root: TreeNode) -> bool:
        if not root:
            return True
        self.tar = root.val  # 目标值
        return self.judge(root)
    
    def judge(self, root):
        if root == None:
            return True
        if root.val == self.tar:
            return self.judge(root.left) and self.judge(root.right)
        return False

问题描述:【DFS、Tree】1022. Sum of Root To Leaf Binary Numbers
解题思路:

这道题是给一个 01 二叉树,计算从根到叶子所有二进制路径表示的十进制数字的总和。

方法1(回溯法):

第一种容易想到的方法就是 DFS 回溯法,对树进行深度优先搜索,将每条路径 path 保存在 paths 列表中,每次找到一条路径的出口是遇到叶子结点。最后,对 paths 进行遍历,将每条路径 path 中的二进制转化为十进制数进行累加(如 int("0101", 2) = 5)。这样做的空间复杂度为 O(n)。

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 sumRootToLeaf(self, root: TreeNode) -> int:
        def findPath(root, path):
            if not root:
                return
            path += str(root.val)  # 往当前路径中添加当前结点
            if root.left == None and root.right == None:  # 到叶子结点,增加一条路径
                paths.append(path)
                return
            findPath(root.left, path)
            findPath(root.right, path)
        
        paths, sum = [], 0  # paths 保存每条路径
        findPath(root, "")
        for path in paths:
            sum += int(path, 2)   # 二进制转十进制
        return sum

方法2(不使用额外空间的做法):

有没有不使用额外空间的做法呢?当然有。可以使用前缀和 presum。

在深度优先搜索的过程中,每增加一层,就修改当前路径的累加值,即 presum = presum * 2 + root.val如 1->0->1 (5)再碰到 1 就会执行 presum = presum * 2 + 1 = 11,刚好是 1->0->1->1(11)。

具体做法如下: 1、如果 root 为空,返回 0; 2、更新前缀累加和 presum = presum * 2 + 1; 2、如果 root.left 或者 root.right 不为空,就递归求解左右子树路径和 return pathSum(root.left, presum) + pathSum(root.right, presum) 3、最后返回 presum 就是答案;

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 sumRootToLeaf(self, root: TreeNode) -> int:
        def pathSum(root, presum):
            if not root:
                return 0
            presum = presum * 2 + root.val  # 每增加一层修改当前路径累加值
            if root.left or root.right:  # 左右子树路径之和
                return pathSum(root.left, presum) + pathSum(root.right, presum)
            return presum  # 到叶子结点
        
        return pathSum(root, 0)

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SUMO学习笔记(1)

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

    嘘、小点声
  • 记录一下qemu调试kernel的东西

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

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

    用户4962466
  • Python爬虫有用的库:fake_useragent

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

    远方的星
  • java加密解密

    landv
  • 验证码常用函数备忘

    冰封一夏
  • Android项目实战(八):列表右侧边栏拼音展示效果

    听着music睡
  • MySQL Cases-记录大量waiting for handler commit

    什么是waiting for handler commit查看官方文档,https://dev.mysql.com/doc/refman/8.0/en/gene...

    姚崇
  • CSS3 -- 动画库

    xing.org1^
  • java开发_闹钟

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

    Hongten
  • 014.Redis Cluster搭建及测试

    3个节点的master配置文件,redis_6379.conf,未列出的配置保持默认即可

    CoderJed
  • SQL基础用法(实例二)

    用户1112962
  • (十四)c#Winform自定义控件-键盘(一)

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

    冰封一夏
  • 学生信息管理系统(C实现)

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

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

    冰封一夏
  • Android系统启动——6 SystemServer启动

    SystemServer是Android系统的核心之一,大部分Android提供的服务都运行在这个进程里,SystemServer中运行的服务总共有60多种。为...

    隔壁老李头
  • (六十六)c#Winform自定义控件-图标

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

    冰封一夏
  • 一个基于.NET平台的自动化/压力测试系统设计简述

    AutoTest是一个基于.NET平台实现的自动化/压力测试的系统,可独立运行于windows平台下,支持分布式部署,不需要其他配置或编译器的支持。(本质是一个...

    lulianqi
  • 计算机专用英语词汇1695个词汇表

    特别感谢: 不愿意透露姓名的小虾同学提供的音标部分 1.单词说明:   command n. 命令,指令 [kə'mɑ:nd]   单词拼写 名词 单词含...

    惨绿少年

扫码关注云+社区

领取腾讯云代金券