Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
思路：
一个BST树，如果中序遍历输出，那么一定是从小到大输出的。于是就可以中序遍历二叉树，如果第一次发现一个节点的值比之前访问的节点值小，那么之前的那个节点就是被交换的第一个节点。接着向后访问，如果是第二次找到某个节点的值比之前访问的节点值小，那么这个节点就是被交换的第二个节点。这是因为第一次找到的是交换顺序中比较大的，第二次是比较小的。但是有一个问题，如果两个节点相邻就会出问题，只能找到一个。仔细分析，如果交换的是两个相邻的节点，第一个节点是访问之前的节点，第二个自然是当前访问的节点。所以，不管怎样，只要满足一个节点的值比之前访问的节点值小，被交换的第二个节点一定是当前访问的节点。
题解：
/** * 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 *pre, *p, *q; void inorder(TreeNode *root) { if(!root) return; inorder(root->left); if(pre && pre->val > root->val) { if(!p) p = pre; q = root; } pre = root; inorder(root->right); } void recoverTree(TreeNode *root) { if(!root) return; pre=p=q=NULL; inorder(root); swap(p->val,q->val); } };
[leetcode] Recover Binary Search Tree
原文：http://www.cnblogs.com/jiasaidongqi/p/4277067.html
