题目

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2
Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3
Follow up:
A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

解法

中序遍历，DFS，注意因为时间复杂度的要求，需要记录每次的上一个节点记录。
根据题目描述, 仅有2个节点的值被交换, 并且暗示用On空间来解决;
所以自然想到把所有值遍历到一个vector里面, 由于是bst, 所以一定是升序, 我们只要找到不符合条件的两个值即可, 最后在tree里面修复;
那么follow up 要求不能使用On空间; 也比较明显了, 直接遍历tree就好了, 不需要vector;

这里要解决的问题就是vector具有随机访问能力, 而bst没有, 用一个技巧来解决, 用一个遍历保存上一个访问的TreeNode; 注意用中序遍历
再来看交换节点有两种情况:
假设数组是12345
1 交换后得到 15342 可以找到 5>3 和 4>2 两个特例
2 得到 13245 只有3>2 一个特例
所以使用vector<pair<TreeNode*>> 保存所有找到的特例; 最后交换TreeNode即可

class Solution {
    //思路：中序遍历找不同，然后换，但是由于对空间复杂度的要求，遍历不输出，为了比较上一个值与当前遍历节点的值，需要进行记录。
public:
    vector<pair<TreeNode*,TreeNode*>> errnum;
    TreeNode* last=nullptr;
    void traverse(TreeNode* root)
    {
        if(root==nullptr)
            return;
        traverse(root->left);
        if(last && last->val>root->val)
            errnum.push_back(make_pair(last,root));
        last=root;
        traverse(root->right);
    }
    void recoverTree(TreeNode* root) {
        traverse(root);
        if(errnum.size()==1)
            swap(errnum[0].first->val,errnum[0].second->val);
        else
            swap(errnum[0].first->val,errnum[1].second->val);  
      
    }
};