leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1305.cpp (1597B)

0 // Not using BST property at all 1 class Solution { 2 void travel(TreeNode *root, multiset<int> &s) { 3 stack<TreeNode *> st; 4 while (true) { 5 while (root) { 6 if (root->right) st.push(root->right); 7 s.insert(root->val); 8 root = root->left; 9 } 10 if (st.empty()) break; 11 root = st.top(), st.pop(); 12 } 13 } 14 15 public: 16 vector<int> getAllElements(TreeNode *root1, TreeNode *root2) { 17 vector<int> res; 18 multiset<int> s; 19 travel(root1, s), travel(root2, s); 20 for (int n : s) 21 res.push_back(n); 22 return res; 23 } 24 }; 25 26 // Using BST property to travel both trees in-order 27 class Solution { 28 void advance(TreeNode *root, stack<TreeNode *> &st) { 29 while (root) { 30 st.push(root); 31 root = root->left; 32 } 33 } 34 35 void append(vector<int> &res, stack<TreeNode *> &st) { 36 res.push_back(st.top()->val); 37 TreeNode *tmp = st.top(); 38 st.pop(); 39 advance(tmp->right, st); 40 } 41 42 public: 43 vector<int> getAllElements(TreeNode *root1, TreeNode *root2) { 44 stack<TreeNode *> st1, st2; 45 vector<int> res; 46 advance(root1, st1), advance(root2, st2); 47 48 while (!st1.empty() && !st2.empty()) { 49 if (st1.top()->val > st2.top()->val) 50 append(res, st2); 51 else 52 append(res, st1); 53 } 54 if (st1.empty()) std::swap(st1, st2); 55 while (!st1.empty()) 56 append(res, st1); 57 return res; 58 } 59 };