合法二叉搜索树
实例要求
- 实现一个函数,检查一棵二叉树是否为二叉搜索树;
示例 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、当前节点允许的最大值 maxVal
; - 2、函数首先检查
当前节点是否为空
,如果是空节点则直接返回 true,因为空节点满足二叉搜索树的条件; - 3、接着,函数检查当前节点的值是否在允许的范围内,即是否大于 minVal 且小于 maxVal;
- 4、如果不在范围内,则返回 false,表示当前节点不满足二叉搜索树的定义;
- 5、最后,函数通过
递归调用自身
来检查当前节点的左子树和右子树,更新范围值为当前节点的值作为新的上界或下界
; - 6、如果左子树和右子树都是二叉搜索树,则返回 true,否则返回 false;
运行结果