C语言面试题之合法二叉搜索树

本文主要是介绍C语言面试题之合法二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

合法二叉搜索树

实例要求

实现一个函数，检查一棵二叉树是否为二叉搜索树；

示例 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；