day146—递归—验证二叉搜索树（LeetCode-98）

题目描述

给你一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

• 节点的左子树只包含严格小于当前节点的数。
• 节点的右子树只包含严格大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104]内
• -231 <= Node.val <= 231 - 1

解决方案：

这段代码的核心功能是判断一棵二叉树是否为有效的二叉搜索树（BST）（满足：左子树所有节点值 < 当前节点值 < 右子树所有节点值，且左右子树也必须是 BST），采用「递归 + 上下界约束」的思路逐节点校验，时间复杂度O(n)（n为节点数），空间复杂度O(h)（h为树的高度），是该问题的经典最优解法。

核心逻辑

代码的核心是为每个节点设定严格的数值上下界，递归校验节点值是否在合法区间内，同时将约束传递给左右子树：

1. 递归辅助函数f：参数为当前节点node、当前节点值的下界l（左边界）、上界r（右边界）：
   • 边界条件：空节点直接返回true（空树是合法的 BST）；
   • 当前节点值校验：取出节点值dx，若dx小于等于下界l或大于等于上界r，说明违反 BST 规则，返回false；
   • 递归校验子树：
     • 左子树的上下界更新为(l, dx)（左子树所有节点值必须 < 当前节点值dx）；
     • 右子树的上下界更新为(dx, r)（右子树所有节点值必须 > 当前节点值dx）；
     • 只有左右子树都合法，才返回true；
2. 主函数isValidBST：
   • 调用辅助函数时，为根节点设定初始上下界：下界为LLONG_MIN（long long 类型的最小值）、上界为LLONG_MAX（long long 类型的最大值），覆盖所有整数范围，避免数值溢出；
   • 最终返回辅助函数的校验结果。

总结

1. 核心思路：通过递归传递上下界约束，而非仅对比当前节点与左右子节点（避免 “仅局部满足、整体不满足” 的错误）；
2. 关键细节：使用LLONG_MIN/LLONG_MAX（需包含<climits>头文件）而非普通 int 极值，防止节点值为 int 最大值 / 最小值时的溢出问题；
3. 效率特点：每个节点仅被校验一次，时间O(n)；递归栈空间取决于树的高度，平衡树为O(log n)，退化为链表时为O(n)。

函数源码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool f(TreeNode* node,long long l,long long r){ if(!node) return true; int dx=node->val; if(l>=dx||dx>=r) return false; return f(node->left,l,dx) && f(node->right,dx,r); } bool isValidBST(TreeNode* root) { return f(root,LLONG_MIN,LLONG_MAX); } };