企业官网建设流程全解析

益阳北京网站建设,vps可以做wordpress和ssr,营销型网站怎么做,成全视频免费观看在线看收索题目描述给你一个二叉树的根节点 root #xff0c;判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下#xff1a;节点的左子树只包含 严格小于 当前节点的数。节点的右子树只包含 严格大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1#x…题目描述给你一个二叉树的根节点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_MINlong long 类型的最小值、上界为LLONG_MAXlong 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 dxnode-val; if(ldx||dxr) return false; return f(node-left,l,dx) f(node-right,dx,r); } bool isValidBST(TreeNode* root) { return f(root,LLONG_MIN,LLONG_MAX); } };