98.验证二叉搜索树

题目
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

字符串转TreeNode的方法

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

TreeNode* stringToTreeNode(string input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    //input = input.substr(1, input.length() - 2);
    if (!input.size()) {
        return nullptr;
    }

    string item;
    stringstream ss;
    ss.str(input);

    getline(ss, item, ',');
    TreeNode* root = new TreeNode(stoi(item));
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);

    while (true) {
        TreeNode* node = nodeQueue.front();
        nodeQueue.pop();

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int leftNumber = stoi(item);
            node->left = new TreeNode(leftNumber);
            nodeQueue.push(node->left);
        }

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int rightNumber = stoi(item);
            node->right = new TreeNode(rightNumber);
            nodeQueue.push(node->right);
        }
    }
    return root;
}

思路
1.记录子树的上界和下界，root的左子树一定小于root的值，root的右子树一定大于root的值，然后递归左子树和右子树。

class Solution {
public:
    bool isValidBST(TreeNode* root, long min, long max)
    {
        if (root == NULL) return true;
        if (root->val <= min || max <= root->val) return false;
        return isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max);
    }
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }

};

2、中序遍历二叉树，并记录前继节点

class Solution2 {
    TreeNode* pre = NULL;
public:
    bool isValidBST(TreeNode* root)
    {
        if (root == NULL) return true;
        TreeNode* left = root;
        while (left->left != NULL)
        {
            left = left->left;
        }
        pre = left;
        return isValid(root);
    }
private:
    bool isValid(TreeNode* root)
    {
        if (root == NULL) return true;
        if (!isValid(root->left)) return false;
        if (root != pre && root->val <= pre->val) return false;
        pre = root;
        return isValid(root->right);
    }
};

主程序

int main() {
    string line = "2,1,3";

        TreeNode* root = stringToTreeNode(line);

        bool ret = Solution().isValidBST(root);

        string out = boolToString(ret);
        cout << out << endl;

    return 0;
}