98-验证二叉搜索树

LeetCode 98. Validate Binary Search Tree

LeetCode-98

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

method

按照中序遍历，就相当于在遍历一个有序数组，如果前面一个元素大于或等于当前元素，就说明不是有序的

TreeNode *pre = nullptr;
bool isValidBST(TreeNode* root) {
    if (!root) return true;
    bool left = isValidBST(root->left);
    if (pre && pre->val >= root->val) return false;
    pre = root;     // 记录前一个节点
    bool right = isValidBST(root->right);
    return left && right;
}