leetcode

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

1373.cpp (1508B)

      1 class Solution {
      2     struct record {
      3         int sum, mini, maxi;
      4         record(int su = 0, int mi = INT_MAX, int ma = INT_MIN) : sum(su), mini(mi), maxi(ma) {}
      5     };
      6 
      7   public:
      8     int maxSumBST(TreeNode *root) {
      9         unordered_map<TreeNode *, record> um;
     10         stack<TreeNode *> st;
     11 
     12         int res = 0;
     13         st.push(root);
     14         while (!st.empty()) {
     15             TreeNode *root = st.top();
     16             st.pop();
     17             if (um.count(root)) {
     18                 record &r = um[root];
     19                 if (root->left) {
     20                     if (root->val <= um[root->left].maxi) {
     21                         r.mini = INT_MIN, r.maxi = INT_MAX;
     22                         continue;
     23                     } else
     24                         r.sum += um[root->left].sum;
     25                 }
     26 
     27                 if (root->right) {
     28                     if (root->val >= um[root->right].mini) {
     29                         r.mini = INT_MIN, r.maxi = INT_MAX;
     30                         continue;
     31                     } else
     32                         r.sum += um[root->right].sum;
     33                 }
     34 
     35                 res = max(res, r.sum);
     36                 r.mini = root->left ? um[root->left].mini : root->val;
     37                 r.maxi = root->right ? um[root->right].maxi : root->val;
     38                 continue;
     39             }
     40             um.insert({root, root->val});
     41             st.push(root);
     42             if (root->left) st.push(root->left);
     43             if (root->right) st.push(root->right);
     44         }
     45         return res;
     46     }
     47 };