leetcode

0 class Solution {

1 public:

2 int maxProduct(TreeNode *root) {

3 if (!root) return 0;

4 const unsigned int M = 1000000007;

5 stack<TreeNode *> st;

6 st.push(root);

7 unordered_set<TreeNode *> visited;

8 while (!st.empty()) {

9 TreeNode *root = st.top();

10 st.pop();

11 if (visited.find(root) != visited.end()) {

12 if (root->left) root->val += root->left->val;

13 if (root->right) root->val += root->right->val;

14 root->val %= M;

15 continue;

16 }

17 st.push(root);

18 visited.insert(root);

19 if (root->left) st.push(root->left);

20 if (root->right) st.push(root->right);

21 }

22

23 long long res = 0ll;

24 int total = root->val;

25 st.push(root);

26 while (!st.empty()) {

27 TreeNode *root = st.top();

28 st.pop();

29 if (root->left) {

30 res = max(res, 1ll * root->left->val * (total - root->left->val));

31 st.push(root->left);

32 }

33 if (root->right) {

34 res = max(res, 1ll * root->right->val * (total - root->right->val));

35 st.push(root->right);

36 }

37 }

38 return res % M;

39 }

40 };