leetcode

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

1080.cpp (1440B)

      1 class Solution {
      2   public:
      3     TreeNode *sufficientSubset(TreeNode *root, int limit) const {
      4         stack<pair<TreeNode *, int>> st;
      5         unordered_set<TreeNode *> deleted;
      6 
      7         st.emplace(root, root->val);
      8         while (!st.empty()) {
      9             if (st.top().first) {
     10                 auto [root, sum] = st.top();
     11                 st.emplace(nullptr, 0);
     12                 if (root->left) st.emplace(root->left, sum + root->left->val);
     13                 if (root->right) st.emplace(root->right, sum + root->right->val);
     14                 continue;
     15             }
     16 
     17             st.pop();
     18             auto [root, sum] = st.top();
     19             st.pop();
     20 
     21             if (!root->left && !root->right) {
     22                 if (sum < limit) deleted.insert(root);
     23             } else {
     24                 int children = 0, del = 0;
     25                 if (root->left) {
     26                     children++;
     27                     if (deleted.count(root->left)) {
     28                         root->left = nullptr;
     29                         del++;
     30                     }
     31                 }
     32                 if (root->right) {
     33                     children++;
     34                     if (deleted.count(root->right)) {
     35                         root->right = nullptr;
     36                         del++;
     37                     }
     38                 }
     39                 if (children == del) deleted.insert(root);
     40             }
     41         }
     42 
     43         return !deleted.count(root) ? root : nullptr;
     44     }
     45 };