题目：传送门
方法转载至 chen

题目中是二叉顺序树两个节点互换，那么就有5种交换可能。

  1. 根结点与左子树上的某个节点互换
  2. 根结点与右子树上的某个节点互换
  3. 左子树上的某个节点与右子树上的某个节点互换
  4. 左子树上的两个节点互换
  5. 右子树的两个节点互换

解决方法

  1. 对于互换1，找到左子树中的最大节点的值与根结点的值比较，若是左子树中的最大节点的值大于根结点的值，则两个节点的值进行交换。
  2. 对于互换2，同上。把左子树中的最大节点的值换成右子树中的最小节点的值，大于换成小于。
  3. 对于互换3，若左子树中的最大节点的值 > 根结点的值 > 右子树中的最小节点的值,左右两节点进行交换。
  4. 对于互换4、5，可把根结点的左右子树看成一颗新树，进行递归。 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
   /*  求左子树中val最大的节点，用于和根结点比较，适用于互换1 */
    void max(TreeNode* root,TreeNode* &big){
        if(!root) return ;
        if(root->val > big ->val){
            big = root;
        }
        max(root->left,big);
        max(root->right,big);

    }
   /*  求右子树中val最小的节点，用于和根结点比较 ，适用于互换2*/
    void min(TreeNode* root,TreeNode* &small){
        if(!root) return ;
        if(root->val < small ->val){
            small = root;
        }
        min(root->left,small);
        min(root->right,small);
    }
    void recoverTree(TreeNode* root) {
        if(!root) return;
        TreeNode* r = root;
        TreeNode *left = root->left ;
        TreeNode *right =  root->right ;
        max(root->left,left);// 求左子树中val最大的节点
        min(root->right,right);//求右子树中val最小的节点
        //互换3，左右互换
        if((left != NULL) && (right != NULL) && (root->val < left->val) && (root->val > right->val) ){
            int val = left->val;
            left->val = right->val;
            right->val = val;
        }
        else if((left != NULL) && (root->val < left->val)){//互换1
            int val = left->val;
            left->val = root->val;
            root->val = val;
        }
        else if( (right != NULL) && (root->val > right->val)){//互换2
            int val = right->val;
            right->val = root->val;
            root->val = val;
        }
        else{//互换4和5
            recoverTree(r->left);
            recoverTree(r->right);
        }
    }
};