验证二叉搜索树
验证二叉搜索树
https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked
LeetCode98:验证二叉搜索树
先说考点:递归
我的理解是,要掌握递归,首先要掌握两个关键点
- 递归是用来处理重复结构的问题
- 用好递归要有大局观,不能只看眼前
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {return isValid(root,Long.MIN_VALUE,Long.MAX_VALUE);}boolean isValid(TreeNode node,long min,long max){if(node==null){return true;}if(node.val<=min||node.val>=max){return false;}return isValid(node.left,min,node.val)&&isValid(node.right,node.val,max);}
}
本质
递归是一种将"大问题"等价拆解"为小问题,并通过自身调用自身来解决问题的思维方式.
递归三要素
| 要素 | 含义 |
|---|---|
| 1. 终止条件 | 什么时候不再调用自身（递归停止）避免无限递归，最常见是：if (node == null) return ... |
| 2. 递归调用 | 函数自己调用自己，把问题不断变小（往子结构“深入”） |
| 3. 返回与组合 | 如何用子问题的结果构造当前问题的答案（通常是 return ... + ... / 合并左右子树结果） |
那什么时候适合用递归呢?
灵魂两问
| 问题 | 意义 |
|---|---|
| 问题是否具有自相似结构？ | 比如：树、链表、数组分割等 |
| 当前问题能否被分解为子问题，并组合子问题的结果？ | 如果能，用递归就对了 |
常见的适用于递归的场景
| 场景 | 示例题 | 特征 |
|---|---|---|
| 树的遍历 | 前中后序、判断 BST、树深度等 | 子结构 = 子树 |
| 分治类算法 | 快排、归并、二分、汉诺塔 | 拆成两个子问题 |
| 回溯 | 全排列、组合、数独 | 穷举+剪枝 |
| 动态规划（自顶向下） | 斐波那契、背包问题 | 用备忘录剪枝 |
| 图的 DFS/BFS | 岛屿数量、染色问题、拓扑排序等 | 图结构递归遍历 |
如何找到递归的终止条件?
方法一：从结构上找“底层单位”
- 树：当节点为 null，表示到了叶子节点底部
- 数组：当索引越界或只有一个元素
- 数：当 n == 1 或 n == 0
- 回溯：当字符串走完 / 组合长度达到目标
方法二：从目标分解角度反推“不能再分的情况”
比如：
- 我要从 n 个数字中选出 k 个
- 当,当前组合长度达到 k，就不能再选了（递归终止）
递归模版
// 返回类型可以是 boolean、int、List 等
ReturnType recur(参数...) {// 1. 终止条件if (满足结束条件) {return 结果;}// 2. 递归调用，处理子结构ReturnType left = recur(子问题1);ReturnType right = recur(子问题2);// 3. 合并结果，或做逻辑判断return 合并(left, right);
}谈回此题目
| 元素 | 实现 |
|---|---|
| 终止条件 | if (node == null) return true; |
| 子问题拆解 | 验证左子树和右子树 |
| 递归参数 | min, max 来定义合法范围 |
| 返回结果组合方式 | 左子树是否合法 && 右子树是否合法 |
总结：掌握递归的 4 步策略
| 步骤 | 行动 |
|---|---|
| 识别是否能递归 | 结构是否可拆？子问题能组合？ |
| 明确终止条件 | 到底部 / 组合完成 / 无法再分 |
| 写出递归调用 | 找出下一层的“子结构”传进去 |
| 合并结果 | 看清返回值 → 是 boolean / 数字 / 集合 → 决定怎么组合 |
春景祥云