题目：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.
解析1：利用中序遍历，判断遍历前一个元素的值是否小于后一个元素的值，如果出现了大于等于的情况，则返回 false
代码如下：
// 时间复杂度 O(n)，空间复杂度 O(log n) class Solution { public: bool isValidBST(TreeNode* root) { stack<TreeNode*> s; TreeNode *cur = root, *prev = nullptr; // 借助于栈的中序遍历，核对前一个结点的元素值 // 是否比后一个结点的元素值小 // 当然也可以采用 Morris 中序遍历 while (!s.empty() || cur) { if (cur) { s.push(cur); cur = cur -> left; } else { cur = s.top(), s.pop(); if (prev) { if(prev -> val >= cur -> val) return false; } prev = cur; cur = cur -> right; } } return false; } };解析2：解析2 的方法参考了网址https://github.com/soulmachine/leetcode#leetcode题解题目， 该代码思想很好，但不能在 leetcode 中通过，因为树中的元素也有可能为 INT_MAX或 INT_MIN
代码如下：
// 时间复杂度 O(n)，空间复杂度 O(log n) // 该代码思想很好，但在 leetcode 中无法通过 class Solution { public: bool isValidBST(TreeNode* root) { return isValidBST(root, INT_MIN, INT_MAX); } // 该方法有一个瑕疵就是如果 root -> val 为 INT_MAX 或者 // 为 INT_MIN 时，该代码就为错误代码 bool isValidBST(TreeNode* root, int lower, int upper) { if(!root) return true; if (root-> val < upper && root-> val > lower) return isValidBST(root -> left, lower, root -> val) && isValidBST(root -> right, upper, root -> val); else return false; } };