*二叉树*恢复二叉树（中序遍历应用）

题目详情

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode *firstElem = NULL;
    TreeNode *secondElem = NULL;
    TreeNode *preElem = new TreeNode(INT_MIN);
    void recoverTree(TreeNode *root) {
        inOrderTraverse(root);

        int tmp = firstElem->val;
        firstElem->val = secondElem->val;
        secondElem->val = tmp;

    }
    void inOrderTraverse(TreeNode *root)
    {
        if(root==NULL)
            return ;
        inOrderTraverse(root->left);
        if(firstElem== NULL&&preElem->val>=root->val)
            firstElem  = preElem;
        if(firstElem !=NULL &&preElem->val>=root->val)
            secondElem = root;
        preElem = root;
        inOrderTraverse(root->right);
    }
};