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是什么。BST就是二叉树，并且左子树必定比root小，右子树必定比root大。这样中序遍历之后，一定就是一个递增的序列。所以BST和中序遍历经常挂在一起。
这道题是有两个数交换了。交换之后有可能，一是造成了交换了这个数一种可能造成了两个位置的变化，一是左子树比根大，一是右子树比根小。比如{2，3，1}这种情况，那么交换了2和1，造成了一开始3比2大，是错的，1比3小。另一种可能就是只造成一边出错。比如{4,1,2}，4和2交换了，造成了root和右子树出错。
算法的思路如下，就是中序遍历的时候，记录了每个节点前一个节点。如果pre->val>root->val。这里因为pre不会再被访问到，如果pre之前为空，那么可以给pre赋值，否则下一次赋值很可能就是当前的root。root就一定会被记录下来。通过这种方式来保证找到的两个指针不一样。
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 void recoverTree(TreeNode *root) { 13 n1 = n2 = pre = NULL; 14 inorder(root); 15 if (n1 && n2) swap(n1->val, n2->val); 16 } 17 18 void inorder(TreeNode *root) { 19 if (!root) return; 20 inorder(root->left); 21 if (pre && pre->val > root->val) { 22 if (!n1) n1 = pre; 23 n2 = root; 24 } 25 pre = root; 26 inorder(root->right); 27 } 28 29 private: 30 TreeNode *n1; 31 TreeNode *n2; 32 TreeNode *pre; 33 };
因为使用了中序遍历，那么就需要用到栈，至少也要O(lgn)。如水中的鱼所讲，可以用Morris Traversal代中序遍历用O(1)的空间来做。Morris Traversal在Annie Kim这篇blog讲得很清楚。明天再自己写一遍。
1 class Solution { 2 public: 3 void recoverTree(TreeNode *root) { 4 n1 = n2 = pre = NULL; 5 TreeNode* current = root; 6 7 while (current != NULL) { 8 if (current->left == NULL) { 9 if (pre && pre->val > current->val) { 10 if (!n1) n1 = pre; 11 n2 = current; 12 } 13 pre = current; 14 current = current->right; 15 } else { 16 TreeNode* rightmost = current->left; 17 while (rightmost->right != NULL && rightmost->right != current) rightmost = rightmost->right; 18 if (rightmost->right == NULL) { 19 rightmost->right = current; 20 current = current->left; 21 } else { 22 rightmost->right = NULL; 23 if (pre && pre->val > current->val) { 24 if (!n1) n1 = pre; 25 n2 = current; 26 } 27 pre = current; 28 current = current->right; 29 } 30 } 31 } 32 if (n1 && n2) swap(n1->val, n2->val); 33 } 34 35 private: 36 TreeNode *n1; 37 TreeNode *n2; 38 TreeNode *pre; 39 };
Morris Traversal的思想就是：
1. 从左子树中找到最右的一个数，把它指向当前节点，以便下次访问的时候回溯回当前节点。
2. 如果这个最右节点已经指向当前节点，证明左子树已经访问完了，此时就可以开始访问右子树了。
因为第一次访问构建回溯链，第二次访问去掉回溯链。
Leetcode | Recover Binary Search Tree,布布扣,bubuko.com
Leetcode | Recover Binary Search Tree
原文：http://www.cnblogs.com/linyx/p/3730965.html