学前心理学课程建设网站,百度极速版下载,大商创源码,公司网页设计模板合法二叉搜索树
实例要求
实现一个函数#xff0c;检查一棵二叉树是否为二叉搜索树#xff1b;
示例 1:
输入:2/ \1 3
输出: true
示例 2:
输入:5/ \1 4/ \3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 #xff0c;但是其右子节点值为 4 …合法二叉搜索树
实例要求
实现一个函数检查一棵二叉树是否为二叉搜索树
示例 1:
输入:2/ \1 3
输出: true
示例 2:
输入:5/ \1 4/ \3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 但是其右子节点值为 4 。实例分析
1、递归地检查二叉树是否为二叉搜索树2、在递归的过程中传递了每个节点的值应该满足的最小值和最大值范围3、初始调用时根节点的值的范围为负无穷到正无穷
示例代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/bool isValidBSTUtil(struct TreeNode* root, long long minVal, long long maxVal) {if (root NULL) {return true;}if (root-val minVal || root-val maxVal) {return false;}return isValidBSTUtil(root-left, minVal, root-val) isValidBSTUtil(root-right, root-val, maxVal);
}bool isValidBST(struct TreeNode* root) {return isValidBSTUtil(root, LLONG_MIN, LLONG_MAX);
}代码解释
1、这个实现使用了递归函数 isValidBSTUtil该函数接受三个参数当前节点指针 root、当前节点允许的最小值 minVal、当前节点允许的最大值 maxVal2、函数首先检查当前节点是否为空如果是空节点则直接返回 true因为空节点满足二叉搜索树的条件3、接着函数检查当前节点的值是否在允许的范围内即是否大于 minVal 且小于 maxVal4、如果不在范围内则返回 false表示当前节点不满足二叉搜索树的定义5、最后函数通过递归调用自身来检查当前节点的左子树和右子树更新范围值为当前节点的值作为新的上界或下界6、如果左子树和右子树都是二叉搜索树则返回 true否则返回 false
运行结果
