leetcode

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

1339.cpp (1297B)

      1 class Solution {
      2   public:
      3     int maxProduct(TreeNode *root) {
      4         if (!root) return 0;
      5         const unsigned int M = 1000000007;
      6         stack<TreeNode *> st;
      7         st.push(root);
      8         unordered_set<TreeNode *> visited;
      9         while (!st.empty()) {
     10             TreeNode *root = st.top();
     11             st.pop();
     12             if (visited.find(root) != visited.end()) {
     13                 if (root->left) root->val += root->left->val;
     14                 if (root->right) root->val += root->right->val;
     15                 root->val %= M;
     16                 continue;
     17             }
     18             st.push(root);
     19             visited.insert(root);
     20             if (root->left) st.push(root->left);
     21             if (root->right) st.push(root->right);
     22         }
     23 
     24         long long res = 0ll;
     25         int total = root->val;
     26         st.push(root);
     27         while (!st.empty()) {
     28             TreeNode *root = st.top();
     29             st.pop();
     30             if (root->left) {
     31                 res = max(res, 1ll * root->left->val * (total - root->left->val));
     32                 st.push(root->left);
     33             }
     34             if (root->right) {
     35                 res = max(res, 1ll * root->right->val * (total - root->right->val));
     36                 st.push(root->right);
     37             }
     38         }
     39         return res % M;
     40     }
     41 };