[Leetcode]数据库题目集的最后一天
终于刷完了,芜湖!🛫🛫🛫
这套题目集总体难度不高,适合刚学的时候作为随堂练习。
题目代码我也同步到GitHub
仓库了🎈:https://github.com/Farmer-chong/LearnProcess/tree/master/Leetcode/leetcode-dataStruct-1
验证二叉搜索树
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
解题思路&题解
因为是一颗二叉搜索树,因此每个节点都满足左边小、右边大这个特性。
因此每次判断的时候记录最小值和最大值,然后判断即可。解题思路如下:
- 由题目得知是整型,因此最大最小值分别为最小、最大的整型数值
- 当前节点值和最大最小值比较,错误则返回
F
- 将当前节点的值作为最大、最小值传入左右子树
- 返回左右子树的判断结果
1 | func isValidBST(root *TreeNode) bool { |
两数之和 IV - 输入 BST
给定一个二叉搜索树 root 和一个目标结果 k,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
示例 1:
1 | 输入: root = [5,3,6,2,4,null,7], k = 9 |
示例 2:
1 | 输入: root = [5,3,6,2,4,null,7], k = 28 |
示例 3:
1 | 输入: root = [2,1,3], k = 4 |
示例 4:
1 | 输入: root = [2,1,3], k = 1 |
示例 5:
1 | 输入: root = [2,1,3], k = 3 |
提示:
- 二叉树的节点个数的范围是
[1, 104]
. -104 <= Node.val <= 104
root
为二叉搜索树-105 <= k <= 105
解题思路&题解
这题的解题思路大致和求两数和
差不多,只是将for循环换成了递归遍历,然后利用hashMap
存储已遍历的内容。
1 | func findTarget(root *TreeNode, k int) bool { |
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
1 | 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 |
示例 2:
1 | 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 |
说明:
- 所有节点的值都是唯一的。
p、q
为不同节点且均存在于给定的二叉搜索树中。
解题思路&题解
解题思路:
- 当前节点和
p、q
节点进行比较 - 如果是
p、q
节点、则返回该节点 - 获取左右子树的节点,当左右节点都存在,则证明当前节点为最近的
祖先节点
- 如果只有单一一个节点,则继续将该节点返回
1 | func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { |