LeetCode 98. Validate Binary Search Tree [Medium] [C++] 解題筆記

這題要我們判斷一個 binary tree 是不是 binary search tree。

EX:

         5

       /   \
      1   4
      / \
    3   6

Input: [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.

想法:

    這題只需要利用 inorder traverse ，然後要是前一個數比當前數字還要大的話就返回 false。

另外這題實作要非常小心，紀錄前一個數字用的指標變數 prev 必須是固定的一個指標變數，不可以在遞歸時一直

複製!，因此必須將prev 宣告成全域變數或者是用 call by reference 的方式傳入，避免只改到 local 複製的指標。

完整程式碼:

解法一:

class Solution {
public:
    bool isValid(TreeNode* root, TreeNode* &prev) {
        if (root == NULL) { return true; }
        if (!isValid(root->left, prev)) { return false; }
        if (prev && root->val <= prev->val) { return false; }
        prev = root;
        return isValid(root->right, prev);
    }   
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = NULL;
        return isValid(root, prev);
    }   
};

解法二:

class Solution {
public:
    bool isValid(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
        if (root == NULL) { return true; }
        if (minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val) {
            return false;
        }
        return isValid(root->left, minNode, root) && isValid(root->right, root, maxNode);
    }
    bool isValidBST(TreeNode* root) {
        return isValid(root, NULL, NULL);
    }
};