98. Validate Binary Search Tree

98. Validate Binary Search Tree

題意

• 判斷一個給定的二元樹是否是一個有效的二元搜索樹（Binary Search Tree, BST）

  • 個樹中任何節點的左子樹只包含小於當前節點的值，右子樹只包含大於當前節點的值

  • 左右子樹也都必須是有效的二元搜索樹

限制

• The number of nodes in the tree is in the range [1, 104].

• -2^31 <= Node.val <= 2^31 - 1

解題思路

• 對於 BST 來說，inorder 的結果應該是一個遞增數列，利用這一個特性可以驗證是否滿足

  • 使用指針 prev 來記錄 inorder 中最後訪問的節點，並在遍歷每個節點時更新此記錄

  • 每次遞迴中判斷當前節點的值是否大於前一個節點prev的值

  • 如果左子樹或右子樹不滿足BST的條件，則立即返回false

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    bool valid(TreeNode* root, TreeNode* &prev) {
        if (!root) {
            return true;
        }

        if (!valid(root->left, prev)) {
            return false;
        }

        if (prev && prev->val >= root->val) {
            return false;
        }
        prev = root;
        return valid(root->right, prev);
    }
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return valid(root, prev);
    }
};