leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1305.cpp (1597B)

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