LeetCode 98 Validate Binary Search Tree

LeetCode 98 Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a 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:

  2
 / \
1   3

Binary tree [2, 1, 3], return true.

Example 2:

  1
 / \
2   3

Binary tree [1, 2, 3], return false.

Diffculty
Medium

Similar Problems
[LeetCode 94] Binary Tree Inorder Traversal Medium [LeetCode 333] Largest BST Subtree Medium

Analysis

注意题目中对 BST 的要求，左子节点的值必须小于父节点，右子节点的值必须大于父节点，不能存在等于的情况！

解法1：min/max法

1. 当前节点的值应该满足在 (minVal, maxVal) 之间，也即 minVal < x->val < maxVal。如果该条件不符合，返回 false。
2. 当前节点的左右子节点分别应该满足：（minVal, x->val] 和 [x->val, maxVal)，也即 minVal < leftVal <= x->val 和 x->val <= rightVal < maxVal

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validBST(root, INT_MIN, INT_MAX);
    }

    bool validBST(TreeNode* root, int minVal, int maxVal) {
        if (root == nullptr) return true;
        if (root->val <= minVal || root->val >= maxVal) return false;
        return validBST(root->left, minVal, root->val) && validBST(root->right, root->val, maxVal);
    }
};

注意：上述节点是错的，因为，当父节点的值为 INT_MIN 或者 INT_MAX 的时候，会返回 false，而正确的结果应该是返回 true。

换一种方法，把 INT_MIN 和 INT_MAX 换成 minNode 和 maxNode，最直接把父节点指针而不是父节点的值传给 validBST() 函数，然后通过判断传过去的父节点指针是否为 nullptr 来辅助判断。如下：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validBST(root, nullptr, nullptr);
    }

    bool validBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
        if(!root) return true;
        if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
            return false;
        return validBST(root->left, minNode, root) && validBST(root->right, root, maxNode);
    }
};

解法2：中序遍历 inorder traversal

1. 对一个 BST 进行 inorder traverse，必然会得到一个严格单调递增序列，否则则是 invalid BST。
2. Inorder traverse 时并不需要记录下整个访问过的序列，而只需要保存前一个访问的节点数值就可以了。

注意：同样需要避免跟解法一中那样使用 INT_MIN 或者 INT_MAX 来做比较，还是应该传递父节点指针来赋值比较。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;          // 中序遍历过程中，仅需保存前一个节点的值即可，然后判断当前节点是否比前一个节点小
        return validBST(root, prev);
    }
    bool validBST(TreeNode* node, TreeNode* &prev) {
        if (node == nullptr) return true;
        if (!validBST(node->left, prev)) return false;                  // 中序遍历需要深度优先递归，直到最左的子叶子节点
        if (prev != nullptr && prev->val >= node->val) return false;    // 中序遍历过程中，判断前一个节点比当前节点大
        prev = node;                                                    // 满足中序遍历中对节点大小顺序的要求，把当前节点记录下来
        return validBST(node->right, prev);
    }
};