Description

98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left
subtree
of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]
Output: true
Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 用來定義 LONG_MIN 和 LONG_MAX
#include <stdbool.h>

// 輔助函數，遞迴檢查每個節點是否在有效範圍內

bool isValidBSTHelper(struct TreeNode* root, long min, long max) {
    if (root == NULL) {
        return true; // 空節點自動視為有效
    }
    
    // 節點的值不在允許範圍內則返回 false
    //left subtree須小於當前節點，right subtree需大於當前節點
    if (root->val <= min || root->val >= max) {
        return false;
    }

    // 遞迴檢查left, right subtree
    return isValidBSTHelper(root->left, min, root->val) && 
           isValidBSTHelper(root->right, root->val, max);
}

//判斷binary tree是否為有效的binary search tree
bool isValidBST(struct TreeNode* root) {
    return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
}

Testing

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 用來定義 LONG_MIN 和 LONG_MAX
#include <stdbool.h> // 用來使用 bool, true, false
//定義binary tree node
struct TreeNode {
    int val;
    struct TreeNode *left;//左節點
    struct TreeNode *right;//右節點
};


// 輔助函數，遞迴檢查每個節點是否在有效範圍內

bool isValidBSTHelper(struct TreeNode* root, long min, long max) {
    if (root == NULL) {
        return true; // 空節點自動視為有效
    }
    
    // 節點的值不在允許範圍內則返回 false
    //left subtree須小於當前節點，right subtree需大於當前節點
    if (root->val <= min || root->val >= max) {
        return false;
    }

    // 遞迴檢查left, right subtree
    return isValidBSTHelper(root->left, min, root->val) && 
           isValidBSTHelper(root->right, root->val, max);
}

//判斷binary tree是否為有效的binary search tree
bool isValidBST(struct TreeNode* root) {
    return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
}

// 測試函數
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 測試用例
void testIsValidBST() {
    // 測試案例1: [2,1,3]
    struct TreeNode* root1 = createNode(2);
    root1->left = createNode(1);
    root1->right = createNode(3);
    printf("Test case 1 (should be true): %s\n", isValidBST(root1) ? "true" : "false");

    // 測試案例2: [5,1,4,null,null,3,6]
    struct TreeNode* root2 = createNode(5);
    root2->left = createNode(1);
    root2->right = createNode(4);
    root2->right->left = createNode(3);
    root2->right->right = createNode(6);
    printf("Test case 2 (should be false): %s\n", isValidBST(root2) ? "true" : "false");
}

// 主測試函數
int main() {
    testIsValidBST();
    return 0;
}