leetcode

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

0654.cpp (1002B)

      1 class Solution {
      2     struct record {
      3         TreeNode **parent;
      4         int start, end;
      5         record(TreeNode **p, int s, int e) : parent(p), start(s), end(e) {}
      6     };
      7 
      8   public:
      9     TreeNode *constructMaximumBinaryTree(vector<int> &nums) {
     10         TreeNode *head, tmp;
     11         stack<record> st;
     12 
     13         head = new TreeNode(-1);
     14         st.push({&head->right, 0, (int)nums.size()});
     15         while (!st.empty()) {
     16             auto [root, start, end] = st.top();
     17             st.pop();
     18             while (start < end) {
     19                 int index = -1;
     20                 for (int i = start, maxi = INT_MIN; i < end; i++)
     21                     if (nums[i] > maxi) {
     22                         maxi = nums[i];
     23                         index = i;
     24                     }
     25                 *root = new TreeNode(nums[index]);
     26                 st.push({&(*root)->left, start, index});
     27                 root = &(*root)->right;
     28                 start = index + 1;
     29             }
     30         }
     31         return head->right;
     32     }
     33 };