一般搜索二叉树的题都可以用中序遍历做，今天复习了一下，发现有一些小细节需要注意，总结一下。
（1）首先是一道很直接的题，判断一颗树是否为二叉搜索树。
如
①牛客NC60-判断一颗树是否为搜索二叉树及完全二叉树
②Leetcode 98-验证二叉搜索树
有一种比较常见的错误思路：
用递归的思想，首先判断当前的节点是否满足大于左孩子 && 小于右孩子；若符合，再递归判断它的左右子树是否均为二叉搜索树，写成代码如下：
bool isSerch(TreeNode* root){
if(!root)
return true;
if(root->left && root->left->val >= root->val)
return false;
if(root->right && root->right->val <= root->val)
return false;
return isSerch(root->left)&&isSerch(root->right);
}
但这种只是保证每一个节点大于左孩子、小于右孩子，而不是大于左子树所有节点、小于右子树所有节点，如下图：
它满足上述代码的判断逻辑，但不是二叉排序树。
①正确的思路1：
上边的解法相当于只给左孩子设定了上边界，而左孩子的右孩子没有上边界、只有下边界；
同理，只有右孩子有下边界，右孩子的左孩子没有下边界、只有上边界；
因此应该给左、右子树所有节点都设定上、下两个边界，加两个参数，根节点4会作为左孩子右子树的上边界，及右孩子的左子树的下边界。
比如节点3：上边界是父亲4，
它的右孩子下边界是父亲3，上边界还是祖先节点得来的4，这时6 > 4，false
代码如下：
bool isSearch(TreeNode* root,int lower,int upper){
if(!root)
return true;
if(root->val <= lower ||root->val >=upper)
return false;
return isSearch(root->left,lower,root->val)&&isSearch(root->right,root->val,upper);
}
其中upper、lower的初始值分别为INT_MIN、INT_MAX
②正确的思路2（中序遍历）：
利用二叉排序树的中序遍历是有序的这一特性，
并用preNum保存上一个节点的值，若中途出现 preNum >= curNode->val，返回false
⚠️这里有一点需要特别注意，preNum必须是传引用或全局变量。若是传值，preNum在一个节点的左子树中更新后无法返回该节点，递归到该节点右子树时，preNum仍然是递归至左子树之前的旧值，这里用两个图示意一下。⚠️
①传值（错误的?♂️）
bool isSerch(TreeNode* root, int pre){
if(!root)
return true;
if(!isSerch(root->left,pre))
return false;
if(pre >= root->val)
return false;
return isSerch(root->right,root->val);
}
②全局变量（或传引用）
int pre = INT_MIN;
bool isSerch(TreeNode* root){
if(!root)
return true;
if(!isSerch(root->left))
return false;
if(pre >= root->val)
return false;
pre=root->val;
return isSerch(root->right);
}
（2）第二题如下
牛客NC58-找到二叉搜索树中两个错误的节点
思路：用中序遍历，每次遇到preNum > cur->val的时候按preNum、curNum的顺序记下这两个值；如果对调的两个节点在中序遍历中相邻，只会遇到一次；若不相邻，遇到两次。
例如：
若正确的中序遍历是（题目描述例子为层次遍历）：
1 2 3 4 5 6 7
①对调 3 和 7：
1 2 7 4 5 6 3
7>4，依次记下 7、4
6>3，依次记下6、3
②对调 4 和 5:
1 2 3 5 4 6 7
5>4，依次记下 5、4
不难看出，存pre、cur值的数组中有2个还是4个值，只与对调的数是否相邻有关，与它们是否在中序遍历的第一个、最后一个无关；若是4个，按照要求依次输出第4个、第1个；
若是2个，依次输出第2个、第1个。
代码如下：
vector<int> ans;
int preVal=INT_MIN;
vector<int> findError(TreeNode* root) {
if(!root)
return ans;
solve(root);
if(ans.size()==4)
return{ans[3],ans[0]};
else return {ans[1],ans[0]};
}
void solve(TreeNode* root){
if(!root)
return;
solve(root->left);
if(preVal>root->val){
ans.push_back(preVal);
ans.push_back(root->val);
}
preVal=root->val;
solve(root->right);
}
依然要注意，用全局变量存储preNum，或参数设为传引用。