Validating Binary Search Tree (BST) in C

描述

驗證二元搜尋樹是否有效，有效的二元搜尋樹必須符合下列原則

• 左子樹的值小於根的值
• 右子樹的值大於根的值
• 左右子樹也是二元搜尋樹

範例

• 有效

無節點

單節點

    0
   / \

左右子樹

    2
   / \
  1   3

• 無效
有相同的值

    1
     \
     (1)

右子樹節點的值小於根的值

    10
   / \
  5   15
     / \
   (6)  20

左子樹節點的值大於根的值

    3
     \
     30
    /
   10
     \
     15
       \
      (45)

原理

用中序走訪(inorder traversal)二元搜尋樹取得節點的值會升冪排列，一旦走訪節點的值小於等於前面節點的值，就不是有效二元搜尋樹

實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool validate(struct TreeNode* root, double *last)
{   
    if (root->left)
        if (validate(root->left, last) == false)
            return false;
    
    // Check ascending order
    if (root->val > *last)
        *last = root->val;
    else
        return false;
    
    if (root->right)
        if (validate(root->right, last) == false)
            return false;
    
    // Subtree is valid
    return true;
}

bool isValidBST(struct TreeNode* root){  
    double last = -2147483649; // integer type minimum is -2147483648, last should be able to store integer minimum
    
    if (root == NULL)
        return true;

    return validate(root, &last);
}