leetcode

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

0865.cpp (1394B)

      1 class Solution {
      2   public:
      3     TreeNode *subtreeWithAllDeepest(TreeNode *root) {
      4         int8_t height[1001] = {0};
      5         stack<TreeNode *> s({root});
      6 
      7         TreeNode *res;
      8         int maxi = INT_MIN;
      9         while (!s.empty()) {
     10             TreeNode *root = s.top();
     11             if (root->val >= 0) {
     12                 if (root->left) {
     13                     height[root->left->val] = height[root->val] + 1;
     14                     s.push(root->left);
     15                 }
     16                 if (root->right) {
     17                     height[root->right->val] = height[root->val] + 1;
     18                     s.push(root->right);
     19                 }
     20                 root->val = -root->val - 1;
     21                 continue;
     22             }
     23             s.pop();
     24             root->val = -(root->val + 1);
     25 
     26             if (!root->left && !root->right) {
     27                 if (height[root->val] > maxi) {
     28                     maxi = height[root->val];
     29                     res = root;
     30                 }
     31                 continue;
     32             }
     33 
     34             int8_t l = 0, r = 0;
     35             if (root->left) l = height[root->left->val];
     36             if (root->right) r = height[root->right->val];
     37 
     38             if (l || r) height[root->val] = max(l, r);
     39             if (height[root->val] >= maxi && l == r) {
     40                 maxi = height[root->val];
     41                 res = root;
     42             }
     43         }
     44         return res;
     45     }
     46 };