题目描述
给你一个二叉树的根节点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为树的高度），是该问题的经典最优解法。
核心逻辑
代码的核心是为每个节点设定严格的数值上下界，递归校验节点值是否在合法区间内，同时将约束传递给左右子树：
- 递归辅助函数
f：参数为当前节点node、当前节点值的下界l（左边界）、上界r（右边界）：- 边界条件：空节点直接返回
true（空树是合法的 BST）； - 当前节点值校验：取出节点值
dx，若dx小于等于下界l或大于等于上界r，说明违反 BST 规则，返回false； - 递归校验子树：
- 左子树的上下界更新为
(l, dx)（左子树所有节点值必须 < 当前节点值dx）； - 右子树的上下界更新为
(dx, r)（右子树所有节点值必须 > 当前节点值dx）； - 只有左右子树都合法，才返回
true；
- 左子树的上下界更新为
- 边界条件：空节点直接返回
- 主函数
isValidBST：- 调用辅助函数时，为根节点设定初始上下界：下界为
LLONG_MIN（long long 类型的最小值）、上界为LLONG_MAX（long long 类型的最大值），覆盖所有整数范围，避免数值溢出； - 最终返回辅助函数的校验结果。
- 调用辅助函数时，为根节点设定初始上下界：下界为
总结
- 核心思路：通过递归传递上下界约束，而非仅对比当前节点与左右子节点（避免 “仅局部满足、整体不满足” 的错误）；
- 关键细节：使用
LLONG_MIN/LLONG_MAX（需包含<climits>头文件）而非普通 int 极值，防止节点值为 int 最大值 / 最小值时的溢出问题； - 效率特点：每个节点仅被校验一次，时间
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); } };
