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；