【二叉树】验证二叉搜索树

解题思路：递归解决

递归结束条件：传入结点为NULL

1. 写出两个函数，compLeft和compRight。这两个函数判断比较当前结点左子树和右子树上所有的结点值。compLeft中所有结点值应该比传入的值小，compRight中所有结点值应该比传入的结点大。如果子树上有一个结点的值不符合规则，返回0
2. isValidBST函数返回这两个函数的返回值以及递归自身进入左右子树

//该子树上所有的值都应该小于val
//递归实现：递归结束条件为传入结点为NULL
//返回递归调用自身进入左右子树的结果
int compLeft(struct TreeNode* node, int val) {
    if(!node)
        return 1;
    return (node->val < val) && compLeft(node->left, val) && compLeft(node->right, val);
}
//该子树上所有的值都应该大于val
int compRight(struct TreeNode* node, int val) {
    if(!node)
        return 1;
    return (node->val > val) && compRight(node->left, val) && compRight(node->right, val);
}

bool isValidBST(struct TreeNode* root){
    if(!root)
        return 1;
    return compLeft(root->left, root->val) && compRight(root->right, root->val) && isValidBST(root->right) && isValidBST(root->left);
}

解题思路2：递归解决

1. 创立一个新函数validate，传入的参数为结点，一个最小值和一个最大值。如果当前结点的值小于最小值或者大于最大值则返回0
2. 返回递归进入左右子树的结果，当遍历左子树时，将node→val作为最大值。当遍历右子树时，将node→val作为最小值

int validate(struct TreeNode* node, const long min, const long max) {
    if(!node)
        return 1;
    if(node->val <= min || node->val >= max)
        return 0;
    return validate(node->left, min, node->val) && validate(node->right, node->val, max);
}

bool isValidBST(struct TreeNode* root){
    return validate(root, LONG_MIN, LONG_MAX);
}

解题思路3：数组解决

1. 创建一个函数traversal，中序遍历二叉树，压入所有结点
2. 遍历数组，查看是否为升序

void traversal(struct TreeNode* node, int* arr, int* size) {
    if(!node)
        return;
    traversal(node->left, arr, size);
    arr[(*size)++] = node->val;
    traversal(node->right, arr, size);
}

bool isValidBST(struct TreeNode* root){
    int* arr = (int*)malloc(sizeof(int) * 10000);
    int size = 0;
    if(!root)
        return 1;
    traversal(root, arr, &size);
    int i;
    printf("%d",size);
    for(i = 1; i < size; i++) {
        if(arr[i-1] >= arr[i])
            return 0;
    }
    return 1;
}