leetcode

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

0124.cpp (1194B)

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