leetcode

Solution to some Leetcode problems written in C++

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

1373.cpp (1508B)

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