原题（Medium）：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
这题我的第一感觉就是深度搜索，比较根结点与左子结点和右子结点的值，根据比较的结果在决定是返回false还是继续递归。就按着这个思路写了代码，运行才发现题目的意思与我的感觉不同。看第二个示例我们就可以发现怎样才算一个有效的二叉搜索树（注意，这是一个反例）：
就是说结点的左子树的所有结点都要小于当前结点，结点的右子树的所有结点都要大于当前结点。
思路一：递归
这就有点复杂了，于当前结点而言，它的存在是否合理，要看它的父节点，以及父节点再往上的结点，举个例子：
于当前结点而言（值为val），决定其值是否合理的，第一个要看其父节点，这里有两种情况，首先看x这个结点（数字仅为标记结点，并非其当前值），当前结点是其x这个结点的右子结点，那么val必须大于x->val，这是它的下界（不能低于它），那么val的上界呢，就是说它有没有一个不能高于的值，有，因为x这个点有父节点z，且x为该父节点的左子结点，说明x结点为根结点的子树的所有结点的值必须小于z这个结点的值，所以val的上界就是z->val，你可能说这不一定啊，如果z还有父节点zz且z是它的左子结点呢？对，没错，那这样的话val的上界就是结点zz值。如果当前结点是父节点的右子结点，需要保留其上界（即当前结点的上界来自父节点的上界），并设置其下界为父节点的值。
另外一种情况就是当前结点为y这个结点的左子结点，为了更好的说明情况，我们假设val合理，并且当前结点来到了j这个结点上，要想验证j->val是否合理，首先其值不能大于val，即j->val < val，这就是 j->val的的上界，那下界呢？如果val有一个父节点x，因为x的右子结点所形成的子树上的所有结点的值都会大于x->val，那么要想j->val合理，j->val > x->val就必须成立，那么x->val就是它下界。如果当前结点是父节点的左子结点，需要保留其下界（即当前结点的下界来自父节点的下界），并设置其上界为父节点的值。
根结点是一个没有上下界的点，那么要从根结点开始，就要设置其上下界为类型最小值和类型最大值。
我们可以通过递归遍历各结点，并在即将进入某个结点时，设置好其上下界（根据上述来决定其上下界的值）。
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 11 bool recursion(TreeNode* root, long lower, long upper) 12 { 13 if (root == NULL) return true; 14 15 int val = root->val; 16 //如果下界存在，且当前值比下界还小，不是二叉搜索树 17 if (lower != LONG_MIN && val <= lower) return false; 18 //如果上界存在，且当前值比上界还大，不是二叉搜索树 19 if (upper != LONG_MAX && val >= upper) return false; 20 21 //即将进入的点是当前结点的右子结点，需要保留其上界（即右子结点的上界来自当前结点的上界），并设置其下界为父结点的值 22 if (!recursion(root->right, val, upper)) return false; 23 //即将进入的点是当前结点的左子结点，需要保留其下界（即左子结点的下界来自当前结点的下界），并设置其上界为父结点的值 24 if (!recursion(root->left, lower, val)) return false; 25 26 return true; 27 } 28 29 bool isValidBST(TreeNode* root) { 30 //根结点是一个没有上下界的点，那么要从根结点开始，就要设置其上下界为类型最小值和类型最大值 31 return recursion(root, LONG_MIN, LONG_MAX); 32 }
至于为什么上下界是long类型，是因为该题中有几个超出整型范围的cases，不得不改为long型。
思路二：中序遍历
这个思路就显浅易懂了，我们应该都知道，一个二叉排序树的中序遍历能够获得其依次递增的数组，应为左子树 -> 结点 -> 右子树 意味着对于二叉搜索树而言，每个元素都应该比下一个元素小。所以，只要我们中序遍历该树，并对得到的数组逐一比较大小，看是否是依次递增就好了。用的是递归。
1 void mid(TreeNode* root, vector<long>& arr) 2 { 3 if(root->left == NULL) 4 { 5 arr.push_back(root->val); 6 if(root->right!=NULL) 7 mid(root->right, arr); 8 return; 9 } 10 else mid(root->left, arr); 11 arr.push_back(root->val); 12 if(root->right!=NULL) 13 mid(root->right, arr); 14 else return; 15 } 16 17 bool isValidBST(TreeNode* root) { 18 if(root == NULL) return true; 19 vector<long> arr; 20 mid(root, arr); 21 for(int i = 1;i <arr.size(); i++) 22 { 23 if(arr[i-1]<arr[i]) continue; 24 return false; 25 } 26 return true; 27 }