1305. All Elements in Two Binary Search Trees
Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.
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 44 45 46 47 48 49 50
|
class Solution { void helper(vector<int>& res, vector<TreeNode*>& st) { res.push_back(st.back()->val); auto node = st.back(); st.pop_back(); if(node->right) { st.push_back(node->right); node = node->right->left; while(node) { st.push_back(node); node = node->left; } } } public: vector<int> getAllElements(TreeNode* root1, TreeNode* root2) { vector<TreeNode*> 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& st = st1.back()->val < st2.back()->val ? st1 : st2; helper(res, st); } while(!st1.empty()) { helper(res, st1); } while(!st2.empty()) { helper(res, st2); } return res; } };
|