Sunday, December 30, 2012

[LeetCode] Recover Binary Search Tree 解题报告

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

[解题报告]
O(n)空间的解法比较直观，中序遍历一遍以后，重新赋值一遍即可，这个解法可以面向n个元素错位的情况。但是对于O(1)空间的解法，最开始的想法是，可以考虑采用类似最大堆的调正过程的算法，但是这样又可能会破坏树的原有结构。暂未想出来解法。

[Code]
``````1:    void recoverTree(TreeNode *root) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      vector<TreeNode*> list;
5:      vector<int > vals;
6:         InOrderTravel(root, list, vals);
7:            sort(vals.begin(), vals.end());
8:            for(int i =0; i< list.size(); i++)
9:            {
10:                 list[i]->val = vals[i];
11:            }
12:    }
13:       void InOrderTravel(TreeNode* node, vector<TreeNode*>& list, vector<int>& vals)
14:       {
15:            if(node == NULL) return;
16:            InOrderTravel(node->left, list, vals);
17:            list.push_back(node);
18:            vals.push_back(node->val);
19:            InOrderTravel(node->right, list, vals);
20:       }
``````

Searched in the web. Actually, there is a smart solution to travel the tree with two node.

``````1:  void Solution::recoverTree(TreeNode *h) {
2:    TreeNode *f1=NULL, *f2=NULL;
3:    bool found = false;
4:    TreeNode *pre, *par = 0; // previous AND parent
5:    while(h) { // Morris Traversal
6:      if(h->left == 0) {
7:        if(par && par->val > h->val) { // inorder previous is: par
8:          if(!found) {
9:            f1 = par;
10:            found = true;
11:          }
12:          f2 = h;
13:        }
14:        par = h;
15:        h = h->right;
16:        continue;
17:      }
18:      pre = h->left;
19:      while(pre->right != 0 && pre->right != h)
20:        pre = pre->right;
21:      if(pre->right == 0) {
22:        pre->right = h;
23:        h = h->left;
24:      } else {
25:        pre->right = 0;
26:        if(pre->val > h->val) { // inorder previous is: pre
27:          if(!found) {
28:            f1 = pre;
29:            found =true;
30:          }
31:          f2 = h;
32:        }
33:        par = h;
34:        h = h->right;
35:      }
36:    }
37:    if(found)
38:      swap(f1->val, f2->val);
39:  }
``````

Update: 3/21/2013  上一个解法不容易看清楚，添加分析。
O(1)的解法就是
Inorder traverse, keep the previous tree node,
Find first misplaced node by
if ( current.val < prev.val )
Node first = prev;

Find second by
if ( current.val < prev.val )
Node second = current;

After traversal, swap the values of first and second node. Only need two pointers, prev and current node. O(1) space.

```1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left```

/* Function to traverse binary tree without recursion and without stack */
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> result;
TreeNode  *current,*pre;

if(root == NULL)
return result;

current = root;
while(current != NULL)
{
if(current->left == NULL)
{
result.push_back(current->val);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;

/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}

/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
result.push_back(current->val);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */

return result;
}

[Code]

void recoverTree(TreeNode *root)
{
TreeNode *f1=NULL, *f2=NULL;
TreeNode  *current,*pre, *parent=NULL;

if(root == NULL)
return;
bool found = false;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
if(parent && parent->val > current->val)
{
if(!found)
{
f1 = parent;
found = true;
}
f2 = current;
}
parent = current;
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;

/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}

/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
if(parent->val > current->val)
{
if(!found)
{
f1 = parent;
found = true;
}
f2 = current;
}
parent = current;
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */

if(f1 && f2)
swap(f1->val, f2->val);
}