leetcode

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 };