本文共 1253 字，大约阅读时间需要 4 分钟。

题目：

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.

解法一：

// Recursion without inorder traversalclass Solution {public:    bool isValidBST(TreeNode *root) {        return isValidBST(root, LONG_MIN, LONG_MAX);    }    bool isValidBST(TreeNode *root, long mn, long mx) {        if (!root) return true;        if (root->val <= mn || root->val >= mx) return false;        return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);    }};

解法二：

// Recursionclass Solution {public:    bool isValidBST(TreeNode *root) {        if (!root) return true;        vector
   
     vals;        inorder(root, vals);        for (int i = 0; i < vals.size() - 1; ++i) {            if (vals[i] >= vals[i + 1]) return false;        }        return true;    }    void inorder(TreeNode *root, vector
    
      &vals) {        if (!root) return;        inorder(root->left, vals);        vals.push_back(root->val);        inorder(root->right, vals);    }};
    
   

转载地址：http://uxuoi.baihongyu.com/