99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？ 示例 1： 99. 恢复二叉搜索树 - 图1 输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。 示例 2： 99. 恢复二叉搜索树 - 图2 输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

解题思路1

  1. 使用数组记录整颗树中序遍历的结果。
  2. 遍历数组，找到不满足顺序的两个结点
    1. 如题目中的示例1，中序遍历是321，3就是选取的第一个结点，1是选取的第二个结点。如何选取的？ 其中因为3>2，不满足顺序关系，继续往后遍历，发现3>1且1是最后一个小于3的结点，所以这里把1作为选取的第二个结点。
    2. 题目中的示例2，中序遍历是1324，3就是选取的第一个结点，2是选取的第二个结点。其中因为3>2，不满足顺序关系，继续往后遍历，发现2已经是最后一个小于3的结点，所以这里把2作为选取的第二个结点。
  3. 交换上述两个结点的数值

时间复杂度：中序遍历O(n) + 一趟扫描数组O(n) = O(n)
空间复杂度：树的递归深度O(h) + 数组 O(n) = O(n) 

  1. class Solution {
  2. public:
  3.     vector<TreeNode*> vec;
  4.     void recoverTree(TreeNode* root) {
  5.         travlInorder(root);
  6.         int j;
  7.         for(int i=1;i<vec.size();i++){
  8.             j = i;
  9.             while(j < vec.size() && vec[j]->val < vec[i-1]->val){ j++;}
  10.             if(vec[j-1]->val < vec[i-1]->val){
  11.                 swap(vec[j-1]->val,vec[i-1]->val);
  12.                 return;
  13.             }
  14.         }
  15.     }
  17.     void travlInorder(TreeNode* root) {
  18.         if(root == NULL)
  19.             return;
  20.         travlInorder(root->left);
  21.         vec.push_back(root);
  22.         travlInorder(root->right);
  23.     }
  24. };

解题思路2

  1. 在中序遍历的过程中记录当前遍历到的中序遍历的最后一个结点pred
  2. 比较pred和当前结点root的大小
    1. 如果pred > root ，则不满足顺序关系，令 x = pred(第一次不满足顺序的pred)， y = root
  3. 交换x和y结点的数值

时间复杂度：中序遍历O(n) = O(n)
空间复杂度：树的递归深度O(h) = O(h) 

class Solution {
public:
    TreeNode* x = NULL;TreeNode* y = NULL;
    TreeNode* pred = NULL;
    void recoverTree(TreeNode* root) {
        travlInorder(root);
        swap(x->val,y->val);
    }
/*
中序遍历
pred是当前中序遍历序列的最后一个结点或者说是遍历到当前结点的中序遍历前驱
x和y是不满足顺序关系的两个待交换的结点
*/
    void travlInorder(TreeNode* root) {
        if(root == NULL)  return;
        travlInorder(root->left);
        if(pred != NULL && pred->val > root->val){
            x = (x == NULL)? pred: x;//x等于第一个不满足顺序关系的前驱结点
            y = root;//y是当前结点
        }
        pred = root;
        travlInorder(root->right);
    }
};