https://leetcode.com/problems/validate-binary-search-tree/
本题要检查BST是否合法。我们知道对BST做中序遍历会得到一个有序序列，所以我们可以中序遍历BST，对各节点保存前序节点，然后检查各节点是否大于其前序节点即可。以下代码的时间复杂度是O(n)，空间复杂度也是O(n)。
class Solution {
TreeNode* m_pre;
public:
Solution()
{
m_pre = NULL;
}
bool isValidBST(TreeNode* root)
{
if(root == NULL)
return true;
bool left = isValidBST(root->left);
if(m_pre!=NULL && root->val <= m_pre->val)
return false;
m_pre = root;
return left && isValidBST(root->right);
}
};
class Solution:
def __init__(self):
self.m_pre = None
def isValidBST(self, root):
if root == None:
return True
left = self.isValidBST(root.left)
if self.m_pre is not None and self.m_pre.val >= root.val:
return False
self.m_pre = root
return left and self.isValidBST(root.right)
