Recover Binary Search Tree@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem

这道题思路很巧妙。刚开始我想穷举所有的情况，然后swap two nodes，后来发现这样做太不现实了。并且code很冗长。在网上看到说用in-order，刚开始没想到关in-order啥事儿。后来想到，因为是binary search tree,所以 in-order traverse得到的array应该是一个递增序列，这样我们就可以把这棵树看作一个array，然后只是其中两个点儿被swap了，找到这两个点，再swap回来就好，这样就不用考虑那些各种情况了。

用2个pointer，一个是pre，一个是current，若是current->val<pre->val, 那么纪录下cur, 遇到下一个再纪录下cur。以免遇到只有两个点儿的情况，要判断一下要不要纪录pre。

然后就是in-order traverse的变体。
还有一个分析得比较多的解法，可以看看 http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void proc(TreeNode *root, TreeNode *&n1, TreeNode *&n2, TreeNode *&prev)
	{
	if(!root)
	return;
	proc(root->left,n1,n2,prev);
	if(prev && prev->val > root->val)
	{
	n2 = root;
	if(!n1)
	n1 = prev;
	}
	prev = root;
	proc(root->right,n1,n2,prev);
	}
	void recoverTree(TreeNode *root) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	TreeNode *n1 = NULL;
	TreeNode *n2 = NULL;
	TreeNode *prev = NULL;
	proc(root,n1,n2,prev);
	if(n1 && n2)
	swap(n1->val,n2->val);
	}
	};

view raw Recover Binary Tree hosted with ❤ by GitHub