【LeetCode】669. Trim a Binary Search Tree 解题报告（Python）
2024-09-02 17:48:10
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/trim-a-binary-search-tree/description/
题目描述
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Input:
1
/ \
0 2
L = 1
R = 2
Output:
1
\
2
Example 2:
Input:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output:
3
/
2
/
1
题目大意
给定[L,R]区间，进行BST裁剪。只要数值不在该区间的节点，全部都删除。返回的结果应该仍然是个BST.
解题方法
递归
想法很简单了，如果root的值比R大，说明root以及其所有右节点都不在这个区间内，向左边搜索。如果root的值比L小，，说明root以及其所有左节点都不在这个区间内，向右边搜索。如果root正好在这个区间内，那么分别对它的左右子树进行裁剪就好了。
# 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, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if not root:
return None
if root.val > R:
return self.trimBST(root.left, L, R)
elif root.val < L:
return self.trimBST(root.right, L, R)
else:
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
return root
日期
2018 年 11 月 8 日 —— 项目进展缓慢
最新文章
- css常用属性汇总
- Download Excel file with Angular
- MarkdownPad2.5 注册码
- （2）RGB-D SLAM系列- 工具篇（依赖库及编译）
- C#添加dll引用后，添加命名空间出错的解决方案
- [Tex学习笔记]积分平均
- phpmyadmin连接，管理多个mysql服务器
- CentOS 实现自动登陆
- 学习Python必须要知道的常用模块
- Java基础知识强化之集合框架笔记12：Collection集合存储字符串并遍历
- 【2017-05-21】WebForm内置对象：Session、Cookie，登录和状态保持
- html5中的网页结构
- HDU2859 Phalanx （动态规划）
- Aragorn's Story HDU - 3966 -树剖模板
- Maven解决包冲突
- win7 docker Toolbox 启动Docker Quickstart Terminal 失败！
- oracle测试环境表空间清理
- 最长公共子序列（LCS）最长递增子序列（LIS）
- MongoDB With Spark遇到的2个错误，不能初始化和sample重复的key
- python语言中的数据类型之元组