C++ track level sum
We can approach this with order traversal (DFS) or level-order traversal (BFS).\n\n#### DFS\nThis is DFS solution that uses an array to track the sum for each l
We can approach this with order traversal (DFS) or level-order traversal (BFS).\n\n#### DFS\nThis is DFS solution that uses an array to track the sum for each level.\n\n```cpp\nvector<int> sums;\nvoid dfs(TreeNode* r, size_t lvl) {\n  if (r != nullptr) {\n    sums.resize(max(sums.size(), lvl));\n    sums[lvl - 1] += r->val;\n    dfs(r->left, lvl + 1);\n    dfs(r->right, lvl + 1);\n  }\n}\nint maxLevelSum(TreeNode* r) {\n  dfs(r, 1);\n  return distance(begin(sums), max_element(begin(sums), end(sums))) + 1;\n}\n```\n**Complexity Analysis**\n- Time: *O(n)*\n- Memory: *O(h)* for the stack and to store sums for each level. This could be O(n) in the worst case (when the tree is a vine).\n\n#### Level-Order Traversal\nSince we process the entire level before moving down, we do not need an array to accumulate sums for each level.\n```cpp\nint maxLevelSum(TreeNode* r) {\n  vector<TreeNode*> q{r};\n  int lvl = 0, msum_lvl = 0, msum = INT_MIN;\n  while (!q.empty()) {\n      vector<TreeNode*> q1;\n      int sum = 0;\n      ++lvl;\n      for (auto n : q) {\n          sum += n->val;\n          if (n->left != nullptr) \n              q1.push_back(n->left);\n          if (n->right != nullptr) \n              q1.push_back(n->right);\n      }\n      msum_lvl = sum > msum ? lvl : msum_lvl;\n      msum = max(sum, msum);\n      swap(q, q1);\n  }\n  return msum_lvl;\n}\n```\n**Complexity Analysis**\n- Time: *O(n)*\n- Memory: *O(n / 2)* to process all nodes in the level. *n / 2* is the number of nodes in the last level of the full tree.
[]