【力扣100题】33.验证二叉搜索树

一、题目描述给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义节点的左子树只包含严格小于当前节点的数节点的右子树只包含严格大于当前节点的数所有左子树和右子树自身必须也是二叉搜索树示例示例输入输出示例1root [2,1,3]true示例2root [5,1,4,null,null,3,6]false示例1有效BST 示例2无效BST 2 5 / \ / \ 1 3 ← 符合BST 1 4 ← 右子树包含3不大于5 / \ 3 6 ← 3不大于4违反BST规则提示树中节点数目范围在[1, 10^4]内-2^31 Node.val 2^31 - 1二、解题思路总览方法核心思想时间复杂度空间复杂度递归隐式栈中序遍历 前驱节点比较O(n)O(h)h为树高核心思想BST的中序遍历得到升序序列遍历过程中记录前驱节点与当前节点比较如果前驱节点值 当前节点值说明不是升序不是BST为什么中序遍历BST的左子树 根 右子树中序遍历顺序左-根-右正好是升序升序中断就说明不是BST三、完整代码classSolution{public:TreeNode*preNULL;// 1. 记录前驱节点boolisValidBST(TreeNode*root){if(!root)returntrue;// 2. 空树是BST// 3. 递归检查左子树boolleftisValidBST(root-left);// 4. 比较前驱节点与当前节点// 中序遍历保证左 根 右// 如果前驱 当前说明不是升序不是BSTif(pre!NULLpre-valroot-val)returnfalse;// 5. 更新前驱为当前节点preroot;// 6. 递归检查右子树boolrightisValidBST(root-right);// 7. 左子树和右子树都必须为BSTreturnleftright;}};四、算法流程图ASCII中序遍历验证过程示例1的BST[2,1,3] 是有效的 2 / \ 1 3 中序遍历过程 遍历顺序1 → 2 → 3升序 pre的变化NULL → 1 → 2 → 3 每次比较pre.val current.val ✓ 示例2的树[5,1,4,null,null,3,6] 不是有效的BST 5 / \ 1 4 / \ 3 6 中序遍历过程 遍历顺序1 → 5 → 3 → 4 → 6 pre的变化NULL → 1 → 5 → 3 发现问题pre(5).val current(3).val ✗ → 返回false递归展开过程以示例1为例isValidBST(2) │ ├── isValidBST(1) ← 左子树 │ │ │ ├── isValidBST(NULL) → true │ │ │ ├── pre NULL, root-val 1 │ │ pre ! NULL? No → 继续 │ │ │ ├── pre 1 │ │ │ └── isValidBST(NULL) → true │ ├── pre 1, root-val 2 │ pre ! NULL? Yes │ pre.val(1) root.val(2)? No → 继续 │ ├── pre 2 │ └── isValidBST(3) ← 右子树 │ ├── isValidBST(NULL) → true │ ├── pre 2, root-val 3 │ pre ! NULL? Yes │ pre.val(2) root.val(3)? No → 继续 │ └── pre 3 最终返回true true true true五、逐行解析classSolution{public:// ─────────────────────────────────────────// 全局变量 pre记录中序遍历的前驱节点// 初始化为 NULL// ─────────────────────────────────────────TreeNode*preNULL;// ─────────────────────────────────────────// 中序遍历验证BST// 左-根-右 的顺序保证遍历结果是升序// ─────────────────────────────────────────boolisValidBST(TreeNode*root){// ─────────────────────────────────────────// 第1步递归终止条件// 空树是有效的BST// ─────────────────────────────────────────if(!root)returntrue;// ─────────────────────────────────────────// 第2步递归检查左子树// 左子树必须是BST// ─────────────────────────────────────────boolleftisValidBST(root-left);// ─────────────────────────────────────────// 第3步比较前驱节点与当前节点//// 中序遍历保证遍历结果是升序// pre 是当前节点的前驱中序遍历顺序// 如果 pre.val root.val说明不是升序// 不是升序就违反了BST的定义// ─────────────────────────────────────────if(pre!NULLpre-valroot-val)returnfalse;// ─────────────────────────────────────────// 第4步更新前驱节点// 当前节点成为下一个节点的前驱// ─────────────────────────────────────────preroot;// ─────────────────────────────────────────// 第5步递归检查右子树// 右子树必须是BST// ─────────────────────────────────────────boolrightisValidBST(root-right);// ─────────────────────────────────────────// 第6步返回结果// 左子树、右子树、当前节点都符合BST定义才行// ─────────────────────────────────────────returnleftright;}};六、复杂度分析时间复杂度分析复杂度每个节点访问一次O(n)推导n 个节点每个节点访问一次比较、递归。空间复杂度分析复杂度递归调用栈最大深度为树高hO(h)推导最坏情况链表形状h n复杂度 O(n)平衡树情况h log n复杂度 O(log n)七、面试追问 FAQ问题回答为什么用中序遍历BST中序遍历是升序升序中断就说明不是BSTpre初始为什么是NULL第一个节点没有前驱不需要比较为什么要判断pre ! NULL要先判断再访问pre-val避免空指针可以用范围判断吗可以记录每个节点的有效范围 [min, max]如果节点值等于前驱值怎么办应该返回 false因为BST要求严格大于八、相关题目题目难度关键点98. 验证二叉搜索树中等本题94. 二叉树的中序遍历简单中序遍历基础230. 二叉搜索树中第K小的元素中等BST中序遍历99. 恢复二叉搜索树困难中序遍历变形九、总结对比项说明代码行数核心8行时间复杂度O(n)空间复杂度O(h)递归顺序中序遍历左-根-右核心技巧前驱节点比较核心公式BST的中序遍历 升序序列 验证方法遍历过程中比较 pre.val current.val易错点不能只比较左右子节点要确保整个左子树都小于根整个右子树都大于根使用前驱比较时要先判断pre ! NULL