leetcode Recover Binary Search Tree

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?

Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

1

/ \

2      3

/

4

\

5
The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

But serialising bST and then comparing the result to find the swapped value requires O(n) space complexity.But we intend to find O(1) space solution.

We can use in-order traverse to find the swapped element. During the traverse, we can find the element that is smaller than the previous node. Using this method we can find the swapped node. Save it and swap them.

[[code]]czo0OTA6XCINClRyZWVOb2RlKiBub2RlMSA9IE5VTEw7DQpUcmVlTm9kZSogbm9kZTIgPSBOVUxMOw0Kdm9pZCByZWNvdmVyVHJlZSh7WyYqJl19VHJlZU5vZGUqIHJvb3QpIHsNCmlub3JkZXJUcmF2ZXJzZShyb290KTsNCmludCB0bXAgPSBub2RlMS0mZ3Q7dmFsOw0Kbm9kZTEtJntbJiomXX1ndDt2YWwgPSBub2RlMi0mZ3Q7dmFsOw0Kbm9kZTItJmd0O3ZhbCA9IHRtcDsNCn0NCg0KVHJlZU5vZGUgKnByZXYgPSBOVUxMOw0Ke1smKiZdfXZvaWQgaW5vcmRlclRyYXZlcnNlKFRyZWVOb2RlICpyb290KSB7DQppZiAocm9vdCA9PSBOVUxMKQ0KcmV0dXJuOw0KaW5vcmRlclR7WyYqJl19cmF2ZXJzZShyb290LSZndDtsZWZ0KTsNCmlmIChwcmV2ICE9IE5VTEwpIHsNCmlmIChyb290LSZndDt2YWwgJmx0Oz0gcHJldi0mZ3tbJiomXX10O3ZhbCkgew0KaWYgKG5vZGUxID09IE5VTEwpDQpub2RlMSA9IHByZXY7DQpub2RlMiA9IHJvb3Q7DQp9DQp9DQpwcmV2ID0gcm9ve1smKiZdfXQ7DQppbm9yZGVyVHJhdmVyc2Uocm9vdC0mZ3Q7cmlnaHQpOw0KfQ0KXCI7e1smKiZdfQ==[[/code]]

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

<strong>    3
   / \
  9  20
    /  \
   15   7
</strong>

return its level order traversal as:
<strong>[
  [3],
  [9,20],
  [15,7]
]</strong>

vector<vector> levelOrder(TreeNode* root) {
vector<vector> res;
if(!root) return res;
queue<pair<int,TreeNode*>> q;
int lev=0;
q.push(make_pair(lev,root));
map<int,vector> hsh;
while(!q.empty())
{
TreeNode *temp= q.front().second;
int level=q.front().first;
//res[level].push_back(temp->val);
//hsh.insert(make_pair(level,temp->val));
hsh[level].push_back(temp->val);
q.pop();
if(temp->left) q.push(make_pair(level+1,temp->left));
if(temp->right) q.push(make_pair(level+1,temp->right));
}
map<int,vector>::iterator itr=hsh.begin();
while(itr != hsh.end())
{
res.push_back((*itr).second);
itr++;

}
return res;

One thought on “leetcode Recover Binary Search Tree”

Leave a Reply

Your email address will not be published. Required fields are marked *