/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */// morris traversal/******************************************************************************************//* Inorder Traversal（should get ascending seq.）：Analysis:case A: If 2 near nodes swapped，then there will be just 1 Inversion Pair.case B: If 2 nodes not near swapped，then there will be 2 Inversion Pairs.Weather case A or case B, swap the max-value and the min-value of the Inversion Pair(s).*//*****************************************************************************************/class Solution {public:    void recoverTree(TreeNode *root) {        TreeNode *cur, *pre, *node1, *node2;  // node1, node2: Record 2 near nodes        TreeNode *first, *second;  // Record 2 swapping nodes        node1 = node2 = first = NULL;        cur = root;        while(cur) {            if(cur->left == NULL) {                if(node1 == NULL) node1 = cur;                else if(node2 == NULL) node2 = cur;                else { node1 = node2; node2 = cur;}                cur = cur->right;            } else {                pre = cur->left;                while(pre->right && pre->right != cur) pre = pre->right;                if(pre->right == NULL) {                    pre->right = cur;                    cur = cur->left;                    continue;                } else {                    pre->right = NULL;                    if(node2 == NULL) node2 = cur;                    else {node1 = node2; node2 = cur;}                    cur = cur->right;                }            }            if(node1 && node2 && node1->val > node2->val) {                if(first == NULL)  first = node1;                second = node2;            }        }        // already learn that there exist 2 nodes swapped.        int t = first->val;        first->val = second->val;        second->val = t;    }};

class Solution {public:bool isValidBST(TreeNode *root) {    if(root == NULL) return true;    TreeNode *pre = NULL, *post = NULL;    if(root->left) {        pre = root->left;        while(pre->right) pre = pre->right;        if(pre->val >= root->val) return false;    }    if(root->right) {        post = root->right;        while(post->left) post = post->left;        if(post->val <= root->val) return false;    }    return isValidBST(root->left) && isValidBST(root->right);}};

bool isBST(TreeNode *root, int& preV) {     if(root == NULL) return true;     bool l = isBST(root->left, preV);     if(preV != INT_MIN && preV >= root->val) return false;     preV = root->val;     bool r = isBST(root->right, preV);     return l && r;}class Solution {public:   bool isValidBST(TreeNode *root) {       int preV = INT_MIN;  // There exists an Assert.         return isBST(root, preV);   }};

class Solution {public:    void recoverTree(TreeNode *root) {        TreeNode *cur, *tem, *node1, *node2;        TreeNode *first, *second;        node1 = node2 = first = NULL;        cur = root;        while(cur) {            if(cur->left == NULL) {                if(node1 == NULL) node1 = cur;                else if(node2 == NULL) node2 = cur;                else { node1 = node2; node2 = cur;}                cur = cur->right;            } else {                tem = cur->left;                while(tem->right && tem->right != cur) tem = tem->right;                if(tem->right == NULL) {                    tem->right = cur;                    cur = cur->left;                    continue;                } else {                    tem->right = NULL;                    if(node2 == NULL) node2 = cur;                    else {node1 = node2; node2 = cur;}                    cur = cur->right;                }            }            if(node1 && node2 && node1->val > node2->val) {                        if(first == NULL)  first = node1;                second = node2;            }        }        int t = first->val;        first->val = second->val;        second->val = t;    }};