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;

Resolving technical problems:

Solve your technical problems instantly

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at writeulearn@gmail.com along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.

One thought on “leetcode Recover Binary Search Tree”

Leave a Reply

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