LeetCode | 0669. 修剪二叉搜索树【Python】
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】 相关文章
- LeetCode | 0662. 二叉树最大宽度【Python】
问题 力扣 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入
- LeetCode | 0655. 输出二叉树【Python】
问题 力扣 在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则： 行数 m 应当等于给定二叉树的高度。 列数 n 应当总是奇数。 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和
- 【栈和队列】leetcode150——逆波兰表达式求值
编号150： 逆波兰表达式求值 根据 逆波兰表示法 ，求表达式的值。 有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明： 整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值
- 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
- [Leetcode]6. Z 字形变换
题目描述 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行Z 字形排列。 比如输入字符串为 "PAYPALISHIRING"行数为 3 时，排列如下： P A H NA P L S I I GY I R 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："P
- 算法：一道题学会位操作和子集运算（LeetCode1178）
算法：一道题学会位操作和子集运算 目录 算法：一道题学会位操作和子集运算 题目 朴素解法 哈希+子集解法 参考 题目 1178. 猜字谜 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。 字谜的迷面 puzzle 按字符串形式给出，如果一个单词 w
- leetcode刷题笔记-297. 二叉树的序列化与反序列化（java实现）
题目描述 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。 请设计一个算法来实现二叉树的序列化与反序列化。这里不限
- LeetCode 30. 串联所有单词的子串
题目: 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。 示例 1： 输入： s = "barfoothe
- 疑问Leetcode/数组/两数之和
题目 给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1： 输入：nums =
- 【栈和队列】leetcode20——有效的括号
编号20：有效的括号 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1:输入: "()"输出: true