LeetCode | 0669. 修剪二叉搜索树【Python】

作者:神秘网友 发布时间:2021-02-27 12:20:39

LeetCode | 0669. 修剪二叉搜索树【Python】

问题

力扣

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构(即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在唯一的答案。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

示例 1:

输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]

示例 2:

输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出:[3,2,null,1]

示例 3:

输入:root = [1], low = 1, high = 2
输出:[1]

示例 4:

输入:root = [1,null,2], low = 1, high = 3
输出:[1,null,2]

示例 5:

输入:root = [1,null,2], low = 2, high = 4
输出:[2]

提示:

  • 树中节点数在范围 [1, 104] 内
  • 0 = Node.val = 104
  • 树中每个节点的值都是唯一的
  • 题目数据保证输入是一棵有效的二叉搜索树
  • 0 = low = high = 104

思路

递归

只需考虑根节点需要做什么,其他的交给递归。

代码

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) - TreeNode:
        if not root:
            return
        # 只需考虑根节点需要做什么,其他的交给递归
        # 左边的全部小于low,所以都剪枝
        if root.val  low:
            root = root.right
            root = self.trimBST(root, low, high)
        # 右边的全部大于high,所以都剪枝
        elif root.val  high:
            root = root.left
            root = self.trimBST(root, low, high)
        else:
            root.left = self.trimBST(root.left, low, high)
            root.right = self.trimBST(root.right, low, high)
        return root

链接

GitHub

LeetCode | 0669. 修剪二叉搜索树【Python】 相关文章

  1. LeetCode | 0662. 二叉树最大宽度【Python】

    问题 力扣 给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的null节点也计入

  2. LeetCode | 0655. 输出二叉树【Python】

    问题 力扣 在一个 m*n 的二维字符串数组中输出二叉树,并遵守以下规则: 行数 m 应当等于给定二叉树的高度。 列数 n 应当总是奇数。 根节点的值(以字符串格式给出)应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分(左下部分和

  3. 【栈和队列】leetcode150——逆波兰表达式求值

    编号150: 逆波兰表达式求值 根据 逆波兰表示法 ,求表达式的值。 有效的运算符包括 + , - , * , / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值

  4. Leecode - 实现乘方

    leetcode(java实现) 问题描述: 50.pow(x,y) Implementpow(x,n), which calculatesxraised to the powern(x^n). Example 1: Input: 2.00000, 10Output: 1024.00000 Example 2:Input: 2.10000, 3 Output: 9.26100 Example 3:Input: 2.00000, -2 Output: 0.2

  5. [Leetcode]6. Z 字形变换

    题目描述 将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行Z 字形排列。 比如输入字符串为 "PAYPALISHIRING"行数为 3 时,排列如下: P A H NA P L S I I GY I R 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"P

  6. 算法:一道题学会位操作和子集运算(LeetCode1178)

    算法:一道题学会位操作和子集运算 目录 算法:一道题学会位操作和子集运算 题目 朴素解法 哈希+子集解法 参考 题目 1178. 猜字谜 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏,请你来猜猜看吧。 字谜的迷面 puzzle 按字符串形式给出,如果一个单词 w

  7. leetcode刷题笔记-297. 二叉树的序列化与反序列化(java实现)

    题目描述 序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。 请设计一个算法来实现二叉树的序列化与反序列化。这里不限

  8. LeetCode 30. 串联所有单词的子串

    题目: 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。 示例 1: 输入: s = "barfoothe

  9. 疑问Leetcode/数组/两数之和

    题目 给定一个整数数组 nums和一个整数目标值 target,请你在该数组中找出 和为目标值 的那两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1: 输入:nums =

  10. 【栈和队列】leetcode20——有效的括号

    编号20:有效的括号 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1:输入: "()"输出: true

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词