Merge two BST ‘s
Given two BSTs, return elements of both BSTs in sorted form.
- Time : O(n + m)
- Space : O(d)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| class Solution { public: vector<int> merge(Node *root1, Node *root2) { vector<Node*> st1, st2; vector<int> res; while(root1) { st1.push_back(root1); root1 = root1->left; } while(root2) { st2.push_back(root2); root2 = root2->left; } while(!st1.empty() and !st2.empty()) { auto& mi = (st1.back()->data > st2.back()->data ? st2 : st1); auto node = mi.back(); mi.pop_back(); res.push_back(node->data); node = node->right; while(node) { mi.push_back(node); node = node->left; } } auto& st = (st1.empty() ? st2 : st1); while(!st.empty()) { auto node = st.back(); st.pop_back(); res.push_back(node->data); node = node->right; while(node) { st.push_back(node); node = node->left; } }
return res; } };
|