leetcode

0 class Solution {

1 public:

2 int maxPathSum(TreeNode *root) {

3 if (!root) return 0;

4 int res = INT_MIN;

5

6 unordered_set<TreeNode *> us;

7 stack<TreeNode *> st;

8 while (root) {

9 st.push(root);

10 root = root->left;

11 }

12 while (!st.empty()) {

13 TreeNode *root = st.top();

14 st.pop();

15

16 if (us.find(root) == us.end()) {

17 st.push(root);

18 us.insert(root);

19 root = root->right;

20 while (root) {

21 st.push(root);

22 root = root->left;

23 }

24 } else {

25 int opt = 0, sum = 0;

26 if (root->left) {

27 opt = max(opt, root->left->val), sum += root->left->val;

28 };

29 if (root->right) {

30 opt = max(opt, root->right->val), sum += root->right->val;

31 };

32 res = max(res, root->val + sum);

33 root->val = max(root->val, root->val + opt);

34 res = max(res, root->val);

35 continue;

36 }

37 }

38 return res;

39 }

40 };