Leetcode面试经典150题刷题记录 —— 二叉搜索树篇

2024-01-16 00:20

本文主要是介绍Leetcode面试经典150题刷题记录 —— 二叉搜索树篇,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Leetcod面试经典150题刷题记录-系列
Leetcod面试经典150题刷题记录——数组 / 字符串篇
Leetcod面试经典150题刷题记录 —— 双指针篇
Leetcod面试经典150题刷题记录 —— 矩阵篇
Leetcod面试经典150题刷题记录 —— 滑动窗口篇
Leetcod面试经典150题刷题记录 —— 哈希表篇
Leetcod面试经典150题刷题记录 —— 区间篇
Leetcod面试经典150题刷题记录——栈篇
Leetcod面试经典150题刷题记录——链表篇
Leetcod面试经典150题刷题记录——二叉树篇
Leetcod面试经典150题刷题记录——二叉树层次遍历篇
本篇:Leetcod面试经典150题刷题记录——二叉搜索树篇

Leetcod面试经典150题刷题记录 —— 二叉搜索树篇

    • 二叉搜索树性质
    • 1. 二叉搜索树的最小绝对差
      • ==脏乱差==版本
      • ==优雅==版本
    • 2. 二叉搜索树中第K小的元素
    • 3. 验证二叉搜索树
      • 经典错误(从局部性质推断全局性质)
      • 利用第1题的代码(有pre指针的那段)
  • 附加题
    • 1. 不同的二叉搜索树

遇到二叉搜索树(BST)的题目,一旦用了sort()直接挂掉面试,切记!

二叉搜索树性质

二叉搜索树的性质满足:
(1)左节点 > root > 右节点 (局部性质)
(2)左子树所有节点 > root > 右子树所有节点 (全局性质,该性质包括局部性质,所以更重要)
相当部分程序员写起上面的局部性质很容易,写全局性质的判断就容易犯病,不瞒你说,我也是。

1. 二叉搜索树的最小绝对差

题目链接:二叉搜索树的最小绝对差 - leetcode
题目描述:
给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。
题目归纳:

解题思路:
解法: 验证二叉搜索树 - leetcode官方题解

脏乱差版本

# 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# 返回二叉搜索树中,任意两个不同节点值之间的最小差值
# 性质
# (1)二叉搜索树。题目既然说了,那么肯定要用到该性质
# (2)任意两个不同节点值,强调了任意两个不同节点。但是既然是二叉搜索树了,拿右子树中的节点 - 左子树中的节点肯定不会是答案,所以这里的任意其实是带引号的"任意",不是绝对的"任意",是可以忽略一些情况的"任意"# 以root节点为例,要查找的目标点一定是下面两种情况
# (1)左树的最右节点 = 左树的最大节点 = 中序遍历的前驱pre节点
# (2)右树的最左节点 = 右树的最大节点 = 中序遍历的后继post节点
# 最后递归搜索
class Solution:def getMinDistance(self, root: Optional[TreeNode]) -> int:if not root: return 0# (1)查找左树的最'右'节点 = 左树的最大节点LR = root.leftwhile LR and (LR.left or LR.right):# 有右边找右边,没右边找左边再找右边if LR.right:LR = LR.rightelse:break# (2)查找右树的最'左'节点 = 右树的最大节点RL = root.rightwhile RL and (RL.left or RL.right):if RL.left:RL = RL.leftelse:breakleft_result = 1e9if LR:            left_result = abs(root.val-LR.val)right_result = 1e9if RL:            right_result = abs(root.val-RL.val)return min(left_result, right_result)def getMinimumDifference(self, root: Optional[TreeNode]) -> int:result = 1e9# 逐个遍历queue = deque([root])while queue:size = len(queue)for i in range(size):node = queue.popleft() if node.left: queue.append(node.left)if node.right: queue.append(node.right)dis = self.getMinDistance(node)result = min(result, dis)return result

优雅版本

# 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 __init__(self):self.result = float('inf')self.pre = Nonedef traversal(self, cur):if cur is None:return Noneself.traversal(cur.left)  # 左if self.pre:  # 中self.result = min(self.result, cur.val - self.pre.val)self.pre = cur  # 记录前一个self.traversal(cur.right)  # 右def getMinimumDifference(self, root):self.traversal(root)return self.result

2. 二叉搜索树中第K小的元素

题目链接:二叉搜索树中第K小的元素 - leetcode
题目描述:
给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。
题目归纳:
中序遍历BST成有序数组,然后再找到这个有序数组的第k个元素?NoNoNo。掌握递归转换成迭代的关键思想,即将"函数调用栈"明写在代码里。

解题思路:
解法: 二叉搜索树中第K小的元素 - leetcode官方题解
中序遍历的迭代写法,注意,非递归!

# 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# 这道题掌握两个知识点
# (1)中序遍历的迭代写法。即将函数调用栈明示出来,因为函数调用栈也是个栈,所有的递归写法都是可以转换为迭代版写法的,手动模拟函数调用栈即可。
# (2)二叉搜索树的中序遍历是有序的。class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:# 中序遍历,迭代版而非递归stack = []while root or stack:# 相当于递归版写法的左子树遍历while root: # 压栈方向是单一的,沿着二叉树的右上角->左下角方向压栈stack.append(root)root = root.leftroot = stack.pop() # 遇到空就出栈# if root: print(root.val)k -= 1if k == 0:return root.valroot = root.right

3. 验证二叉搜索树

题目链接:验证二叉搜索树 - leetcode
题目描述:
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
题目归纳:
右视图 = 右边的侧视图

解题思路:
解法: 验证二叉搜索树 - leetcode官方题解
(1) 从左到右层序遍历。记录层序遍历的最后一个node,即为右视图看到的第一个node。

经典错误(从局部性质推断全局性质)

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:# 这是一道21年的408考研真题,空节点和叶节点都是二叉搜索树# 注意下面的写法是错误的,原因在于只判断了局部的性质,而忽略了全局的性质if not root: return Trueif not root.left and not root.right: return True# (1)这个时候root肯定存在,左树或许存在,结合root与左树根节点,判断是不是二叉搜索树if root and root.left and root.left.val < root.val:return self.isValidBST(root.left)else:return False# (2)这个时候root肯定存在,右树或许存在,结合root与右树根节点,判断是不是二叉搜索树if root and root.right and root.val < root.right.val:return self.isValidBST(root.right)else:return False

利用第1题的代码(有pre指针的那段)

# 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 __init__(self):self.pre = Nonedef isValidBST(self, root: Optional[TreeNode]) -> bool:if not root:return Trueleft = self.isValidBST(root.left)if self.pre and self.pre.val >= root.val: # __比第1题加了这个判断__return Falseself.pre = root # 要遍历root.right了,这个时候记录pre节点right = self.isValidBST(root.right)return left and right # 两边都要是BST树

附加题

1. 不同的二叉搜索树

题目链接:不同的二叉搜索树 - leetcode
题目描述:
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
题目归纳:
分治+动态规划

解题思路:
解法: 不同的二叉搜索树 - leetcode官方题解

class Solution:def numTrees(self, n: int) -> int:# 给一个整数n,求恰好由n个节点组成,且节点值从1到n,能够组成多少种不同的二叉搜索树。#给定一个有序序列1...n,遍历数字i,将数字i作为root,1 ... (i-1)序列作为左子树,(i+1) ... n作为右子树,接着按照同样的方式递归构建左子树和右子树# 在上述构建过程中,由于根root值不同,因此能保证每棵BST是唯一的。# 采用动态规划来求解本题# G(n): 长度为n的序列,所能构成的不同的BST树的个数。注意到 G(n) 和序列的内容无关,只和序列的长度有关# F(i,n):以i为根、序列长度为n的不同BST的个数# G(n) = sum_{1}^{n}F(i,n)# 特别的: G(0) = 1 , G(1) = 1# F(i,n) = G(i-1)*G(n-i)# ==> G(n) = sum_{1}^{n}G(i-1)G(n-i)G = [0] * (n+1)G[0] = 1G[1] = 1for i in range(2, n+1):for j in range(1, i+1):G[i] += G[j-1] * G[i-j]return G[n]

这篇关于Leetcode面试经典150题刷题记录 —— 二叉搜索树篇的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610706

相关文章

关于rpc长连接与短连接的思考记录

《关于rpc长连接与短连接的思考记录》文章总结了RPC项目中长连接和短连接的处理方式,包括RPC和HTTP的长连接与短连接的区别、TCP的保活机制、客户端与服务器的连接模式及其利弊分析,文章强调了在实... 目录rpc项目中的长连接与短连接的思考什么是rpc项目中的长连接和短连接与tcp和http的长连接短

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》:本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI

Python MySQL如何通过Binlog获取变更记录恢复数据

《PythonMySQL如何通过Binlog获取变更记录恢复数据》本文介绍了如何使用Python和pymysqlreplication库通过MySQL的二进制日志(Binlog)获取数据库的变更记录... 目录python mysql通过Binlog获取变更记录恢复数据1.安装pymysqlreplicat

Servlet中配置和使用过滤器的步骤记录

《Servlet中配置和使用过滤器的步骤记录》:本文主要介绍在Servlet中配置和使用过滤器的方法,包括创建过滤器类、配置过滤器以及在Web应用中使用过滤器等步骤,文中通过代码介绍的非常详细,需... 目录创建过滤器类配置过滤器使用过滤器总结在Servlet中配置和使用过滤器主要包括创建过滤器类、配置过滤

正则表达式高级应用与性能优化记录

《正则表达式高级应用与性能优化记录》本文介绍了正则表达式的高级应用和性能优化技巧,包括文本拆分、合并、XML/HTML解析、数据分析、以及性能优化方法,通过这些技巧,可以更高效地利用正则表达式进行复杂... 目录第6章:正则表达式的高级应用6.1 模式匹配与文本处理6.1.1 文本拆分6.1.2 文本合并6

python与QT联合的详细步骤记录

《python与QT联合的详细步骤记录》:本文主要介绍python与QT联合的详细步骤,文章还展示了如何在Python中调用QT的.ui文件来实现GUI界面,并介绍了多窗口的应用,文中通过代码介绍... 目录一、文章简介二、安装pyqt5三、GUI页面设计四、python的使用python文件创建pytho

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。