leetcode

0 class Solution {

1 typedef tuple<int, int> tii;

2

3 public:

4 int averageOfSubtree(const TreeNode *root) const {

5 unordered_map<const TreeNode *, tii> um;

6 stack<const TreeNode *> st;

7 int count = 0;

8 st.push(root);

9 while (!st.empty()) {

10 if (st.top() != nullptr) {

11 const TreeNode *root = st.top();

12 st.push(nullptr);

13 if (root->left) st.push(root->left);

14 if (root->right) st.push(root->right);

15 continue;

16 }

17 st.pop();

18 const TreeNode *root = st.top();

19 st.pop();

20

21 tii left = um[root->left], right = um[root->right];

22 um[root] = {root->val + get<0>(left) + get<0>(right), 1 + get<1>(left) + get<1>(right)};

23 if (get<0>(um[root]) / get<1>(um[root]) == root->val) count++;

24 }

25 return count;

26 }

27 };