说实话，树结构一直是我的弱项，这也体现了我对递归这样的方法不熟（在我看来，树和递归关系很密切）。现在刷题刷到树相关的题目了。题目如标题：验证二叉搜索树。

开始我的思路是：假定当前结点值为k，对于二叉树中每个结点，判断其左子树的值是否小于k，其右子树的值是否大于k。如果所有结点都满足该条件，则该二叉树是一棵二叉搜索树。但是这是错的，比如这样：

  10   /  \  5   15         /  \    6    20 这棵树就满足上面的算法思路，但是这不是二叉搜索树，因为6小于10；所以换一种思路： 暴力破解： 假定当前结点值为k。对于二叉树中每个结点，其左子树所有结点的值必须都小于k，其右子树所有结点的值都必须大于k。 代码：

1 class Solution { 2 public: 3     bool isValidBST(TreeNode* root, int min = INT_MIN, int max = INT_MAX) { 4         if (root == nullptr)                 //终止条件 5         { 6             return true; 7         } 8         return ((Tree_left(root->left, root->val)) && (Tree_Right(root->right, root->val)) && isValidBST(root->left) && isValidBST(root->right)); 9     }10     bool Tree_left(TreeNode *root, int val)11     {12         if (root == NULL)13         {14             return true;15         }16         return ((root->val < val) && (Tree_left(root->left, val)) && (Tree_left(root->right, val)));17     }18     bool Tree_Right(TreeNode*root, int val)19     {20         if (root == NULL)21         {22             return true;23         }24         return ((root->val > val) && (Tree_Right(root->left, val)) && (Tree_Right(root->right, val)));25     }26     int min = INT_MIN, max = INT_MAX;27 };

但是比较慢，最坏的情况是O(n^2)。所以我参考另一种方法：

　　：遍历方向：左节点==>根==>右节点。前面的链接是维基百科，若是不能访问，。

拿前面的那颗树来说：遍历之后的结果就是：5,10,6,15,20.可以很清晰的看出来，6在10后面，不满足从小到大的顺序，即：二叉搜索树的中序遍历之后的结果是一个从小到大的有序集合。 所以，接下来的事情就比较简单了：

1 class Solution { 2 public: 3     bool isValidBST(TreeNode* root) { 4         vector
     
       v; 5         inOrder(root, v); 6         for (int i = 1; i < v.size(); ++ i){ 7             if (v[i - 1] >= v[i]) 8                 return false; 9         }10         return true;11     }12 private:13     void inOrder(TreeNode* root, vector
      
       & v){14         if (root == nullptr) return;15         inOrder(root->left, v);16         v.push_back(root->val);17         inOrder(root->right, v);18     }19     20 };21 static int _____ = [](){22     std::ios::sync_with_stdio(false);23     cin.tie(NULL);24     return 0;25 }();
      
     

inOrder()函数实现中序遍历，接下来就是一个比较循环。代码是别人写的：来源LeetCode：初级算法：树：验证搜索二叉树。 参考：https://blog.csdn.net/sgbfblog/article/details/7771096