LeetCode Q99: Recover Binary Search Tree (hard)

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.

The difficulties of this problem come from the requirement of using O(1) space only. With this requirement, methods based on recursion will not fit. Since the stack used during recursion will take O(n) spaces.

However, just reference of myself. I present the first solution which is based on recursion here.

Solution 1:

The idea of this solution is to traverse the tree using in-order traversal. Check whether nodes visited is in a ascending order. When a node violate the property, we need to save current node and a node just visited before it. Because we so far don't know which node violate the property unless both two violations are detected. It is possible that there is only one violation detected which means the violation happened just between father and son nodes we just recorded.  When there are two violations, we swap the max node of first pair with the min node of the second pair. Done!

	/**
	* 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 helper(TreeNode* node, vector<TreeNode*>& H, TreeNode*& last){
	if(node==NULL)
	return;
	helper(node->left, H, last);
	if(last!=NULL && node->val <= last->val){
	H.push_back(last);
	H.push_back(node);
	}
	last=node;
	helper(node->right, H, last);
	}
	void recoverTree(TreeNode* root) {
	vector<TreeNode*> H;
	TreeNode* last=NULL;
	helper(root, H, last);
	printf("%d\n", H.size());
	if(H.size()==2){
	int tmp=H[0]->val;
	H[0]->val=H[1]->val;
	H[1]->val=tmp;
	}
	if(H.size()==4){
	TreeNode* tmp1 = H[0]->val>H[1]->val? H[0]:H[1];
	TreeNode* tmp2 = H[2]->val<H[3]->val? H[2]:H[3];
	int tmp=tmp1->val;
	tmp1->val=tmp2->val;
	tmp2->val=tmp;
	}
	}
	};

view raw Q99-1.cpp hosted with ❤ by GitHub

Solution 2:

The idea is the same as solution 1. The difference here is to use threaded binary search tree, specifically, Morris traversal, which require O(1) space only and can still be finished in O(n) time. For more details of Morris traversal please see this post.

	class Solution {
	public:
	void helper(TreeNode* node, vector<TreeNode*>& H, TreeNode*& last){
	}
	void inorderMorrisTraversal(TreeNode *root) {
	TreeNode *cur = root, *prev = NULL;
	vector<TreeNode*> H;
	TreeNode* last=NULL;
	while (cur != NULL)
	{
	if (cur->left == NULL) // 1.
	{
	if(last!=NULL && cur->val<=last->val){
	H.push_back(last);
	H.push_back(cur);
	}
	last=cur;
	cur = cur->right;
	}
	else
	{
	// find predecessor
	prev = cur->left;
	while (prev->right != NULL && prev->right != cur)
	prev = prev->right;
	if (prev->right == NULL) // 2.a)
	{
	prev->right = cur;
	cur = cur->left;
	}
	else // 2.b)
	{
	prev->right = NULL;
	if(last!=NULL && cur->val<=last->val){
	H.push_back(last);
	H.push_back(cur);
	}
	last=cur;
	cur = cur->right;
	}
	}
	}
	if(H.size()==2){
	int tmp=H[0]->val;
	H[0]->val=H[1]->val;
	H[1]->val=tmp;
	}
	if(H.size()==4){
	TreeNode* tmp1 = H[0]->val>H[1]->val? H[0]:H[1];
	TreeNode* tmp2 = H[2]->val<H[3]->val? H[2]:H[3];
	int tmp=tmp1->val;
	tmp1->val=tmp2->val;
	tmp2->val=tmp;
	}
	}
	void recoverTree(TreeNode* root) {
	inorderMorrisTraversal(root);
	}
	};

view raw Q99-2.cpp hosted with ❤ by GitHub