一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回他们的值。保证二叉树中结点的值各不相同。
给定一棵树的根结点，请返回两个调换了位置的值，其中小的值在前。
思路：二叉搜索树按照中序遍历应该是一个升序数组，如果有错位节点，包括两种情况 情况1: 1 5 3 4 2，其中共有两次降序数字对，分别为5 3与4 2，只要取第一对的较大数字与第二对的较小数字即可 情况2: 1 2 4 3 5，其中只有一对降序数字，则直接返回即可。
中序遍历当前的二叉树，每次记录上一个数和当前的数进行比较，如果减小了就是出错的数，记第一次出错时的较大值（当前值的前面一个值）为n1，较小值（当前值）为n2，然后继续向下遍历，如果遇到第2次出错的情况，就用较小的值（当前值）替换n2，表示这才是与n1交换的值，最后显然n1，n2就是交换的2个值，并且n1>n2，由于要求返回时较小的值在前面，因此返回n2，n1。可以使用递归也可以不使用递归来解决问题。 总的来说第一个出错的数（大）是第一次减小时前面的数；第二个出错的数（小）是最后一次减小时后面的数。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class FindErrorNode { public: vector<int> findError(TreeNode* root) { vector<int> recur; vector<int> res; inOrderRecur(root,recur); int count=0,big,small; for(int i=0;i<recur.size()-1;i++){ if(recur[i]>recur[i+1]){ //此时出现减小的结点 /*只有第一次出现减小的结点时才设置recur[i]，之后再次遇到减小的情况时不再更新recur[i],只更新recur[i+1]， 因此使用count==0表示是否是第一次遇到减小的情况,从而保证只有第一次出现减小情况时更新recur[i]*/ if(count==0){ //出现第一对降序数字对，存下来 big=recur[i]; small=recur[i+1]; count=1;// }else{//寻找第二对降序数字对，它始终是最后一次减小时的后面的一个数 small=recur[i+1];//更新第二个数为第二对中较小的数字 } //count++; } } res.push_back(small); res.push_back(big); return res; } void inOrderRecur(TreeNode* root,vector<int> &vec) { if(root==NULL) return; inOrderRecur(root->left,vec); vec.push_back(root->val); inOrderRecur(root->right,vec); } };
