leetcode

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

2265.cpp (918B)

      1 class Solution {
      2     typedef tuple<int, int> tii;
      3 
      4   public:
      5     int averageOfSubtree(const TreeNode *root) const {
      6         unordered_map<const TreeNode *, tii> um;
      7         stack<const TreeNode *> st;
      8         int count = 0;
      9         st.push(root);
     10         while (!st.empty()) {
     11             if (st.top() != nullptr) {
     12                 const TreeNode *root = st.top();
     13                 st.push(nullptr);
     14                 if (root->left) st.push(root->left);
     15                 if (root->right) st.push(root->right);
     16                 continue;
     17             }
     18             st.pop();
     19             const TreeNode *root = st.top();
     20             st.pop();
     21 
     22             tii left = um[root->left], right = um[root->right];
     23             um[root] = {root->val + get<0>(left) + get<0>(right), 1 + get<1>(left) + get<1>(right)};
     24             if (get<0>(um[root]) / get<1>(um[root]) == root->val) count++;
     25         }
     26         return count;
     27     }
     28 };