[C++] DFS Solution Explained, 100% Time (Best Time, 112ms), ~90% Space
Nice one and while the BFS approach might be tempting, its memory consumption in a common implementation is definitely less charming, so I opted to go with a DF
Nice one and while the BFS approach might be tempting, its memory consumption in a common implementation is definitely less charming, so I opted to go with a DFS traversal.\n\nTo do so, we will need a few support variables at class level:\n* `store` is an array of values (`40` are enough, as I found by trial and error);\n* `maxLevel` will store the currently maximum level reached.\n\nAnd we will need a few more support variables in our function too:\n* `maxV` to store the maximum value seen so far, initially set to `INT_MIN`;\n* `res` to store our result.\n\nWe will then call the helper function `dfs` on `root`, with `level` defaulted to `0` and this function will:\n* add `root->val` to `store[level]`;\n* update `maxLevel` to be the maximum between its current valuee and `level`;\n* call recursivey `dfs` on `root->left` and `root->right` with increased value for `level`, provided said branches exist.\n\nOnce done, we will parse `store` with `i` from `0` up to `maxLevel` (included) and:\n* if `store[i]` is greater than `maxV`:\n\t* we will update `maxV` to `store[i]`;\n\t* we will store `i` in `res`.\n\nOnce done, we can `return` `res + 1` (since the problem is expecting for us to count levels on a `1`-based counting method) and be done with it :)\n\nThe code:\n\n```cpp\nclass Solution {\n    int store[40] = {}, maxLevel;\n    void dfs(TreeNode *root, int level = 0) {\n        store[level] += root->val;\n        maxLevel = max(level, maxLevel);\n        if (root->left) dfs(root->left, level + 1);\n        if (root->right) dfs(root->right, level + 1);\n    }\npublic:\n    int maxLevelSum(TreeNode *root) {\n        int maxV = INT_MIN, res;\n        dfs(root);\n        for (int i = 0; i <= maxLevel; i++) {\n            if (store[i] > maxV) {\n                maxV = store[i];\n                res = i;\n            }\n        }\n        return res + 1;\n    }\n};\n```\n\nThe brag:\n\n![image](https://assets.leetcode.com/users/images/00e96bbf-2bd2-4581-8836-8eaf1aa4744a_1627758097.801418.png)\n\nThen I wanted to try the BFS way with some trick to optimise performance - ie: ditching the expensive queue approach to rely on nice and shiny arrays of pointers, as I was inspired to do [reading this solution](https://leetcode.com/problems/deepest-leaves-sum/discuss/1374879/).\n\nTo do so, we will declare a few more variables this time:\n* `level` and `nextLevel` are my queue replacements and are just arrays of `TreeNode` values;\n* `currNode` is handy pointer to the node we will be currently parsing in our BFS approach;\n* `currPos` and `nextPos` are pointers to the next cell we are going to write in `level` and `nextLevel`, respectively;\n* `maxTot` and `tot` will store our maximum (initialised to be `INT_MIN`) and current level total respectively;\n* `res` will store our result;\n* `levelCounter` will keep track of what level we are currently parsing, initialised to `1` since this problem counts levels in a `1`-based approach, as mentioned before.\n\nOur BFS routine will go on as long as we have elements to parse, so until `currPos` is not `0` and in it we will:\n* initialise both `tot` and `nextPos` to `0`;\n* parse the current level with `i` going from `0` to `currPos` and:\n\t* assign the value of `store[i]` to `currNode`;\n\t* increase `tot` by `currNode->val`;\n\t* add `currNode->left` and `currNode->right` to `nextLevel` while also increasing `nextPos` accordingly, provided they exist;\n* check if `tot` is greater than any total found before (ie: `> maxTot`) and, in case:\n\t* assign `levelCounter` to `res`;\n\t* update `maxTot` to be `tot`;\n* prepare for the next loop, swapping `level` and `nextLevel` and `currPos` and `nextPos`;\n* reset `nextPos` to `0`;\n* increase `levelCounter` by `1`.\n\nOnce done, we can return `res` :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int maxLevelSum(TreeNode *root) {\n        TreeNode *level[2000], *nextLevel[2000], *currNode;\n        int currPos = 1, nextPos, maxTot = INT_MIN, tot, res, levelCounter = 1;\n        // setting up level\n        level[0] = root;\n        // BFS routine\n        while (currPos) {\n            tot = 0;\n            nextPos = 0;\n            // parsing all the nodes of the current level\n            for (int i = 0; i < currPos; i++) {\n                // increasing tot and populating nextLevel\n                currNode = level[i];\n                tot += currNode->val;\n                if (currNode->left) nextLevel[nextPos++] = currNode->left;\n                if (currNode->right) nextLevel[nextPos++] = currNode->right;\n            }\n            // checking if we encountered a new maximum\n            if (tot > maxTot) {\n                res = levelCounter;\n                maxTot = tot;\n            }\n            // preparing for the next loop\n            swap(level, nextLevel);\n            swap(currPos, nextPos);\n            nextPos = 0;\n            levelCounter++;\n        }\n        return res;\n    }\n};\n```\n\nThe further brag: ![image](https://assets.leetcode.com/users/images/cdb621b4-85ed-4457-8983-8d93dfd526b3_1627764072.436866.png)\n
['Depth-First Search', 'C', 'C++']