98. Validate Binary Search Tree

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 right subtree of a node contains only nodes with keys greater than
• 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.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isValidBST(TreeNode* root) {
    if (root == NULL) return true;
    long long pre = LLONG_MIN;///
    bool valid = true;
    dfs(root, pre,valid);
    return valid;
  }
private:

  void dfs(TreeNode* root, long long& pre, bool& valid){
    if (root->left)
      dfs(root->left, pre,valid);

    if (root->val <= pre){
      valid = false;
      return;
    }
    else
      pre = root->val;

    if (valid&&root->right)
      dfs(root->right, pre,valid);
  }

};

更简洁的方法

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