[LeetCode]Recover Binary Search Tree

Inorder traversal，因为中序遍历保证得到从小到大的序列，我们就可以知道是哪两个节点需要交换。比如：

1. 中序遍历的结果是132，我们可以得知2和3需要交换
2. 中序遍历的结果是15342，我们可以得知5和2需要交换

策略就是，发现reverse pair之后，就假定这两个是需要交换的node1和node2，对应1的情况。如果发现了第二对reverse pair，那么需要交换的就是第一对里的node1和第二对里的node2，时间复杂度O(n)，常数空间，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void recoverTree(TreeNode* root) {
	TreeNode* culprit1 = nullptr, *culprit2 = nullptr, *prev = nullptr;
	recover(root, culprit1, culprit2, prev);
	int temp = culprit1->val;
	culprit1->val = culprit2->val;
	culprit2->val = temp;
	}
	private:
	void recover(TreeNode* curr, TreeNode*& culprit1, TreeNode*& culprit2, TreeNode*& prev)
	{
	if(!curr)return;
	recover(curr->left, culprit1, culprit2, prev);
	if(prev && prev->val > curr->val)
	{
	if(!culprit1)
	{
	culprit1 = prev;
	culprit2 = curr;
	}
	else
	{
	culprit2 = curr;
	}
	}
	prev = curr;
	recover(curr->right, culprit1, culprit2, prev);
	}
	};

view raw Recover Binary Search Tree.cpp hosted with ❤ by GitHub