[C++] 4 Solutions Compared and Explained, 100% Time, 100% Space
Fantastic problem you can tackle from multiple directions - as I did with pleasure :)\n\nMy first approach was to run a plain DFS call to build a vector represe
Fantastic problem you can tackle from multiple directions - as I did with pleasure :)\n\nMy first approach was to run a plain DFS call to build a vector represeting the path up to the node itself and then check if it was one of the deepest one, in order to then take the first and the last of them to find their common ancestor.\n\nTo do so, I declared a couple of variables, at class level:\n* `paths` is a vector of `TreeNode` vectors and it will store all our deeper ones;\n* `tmp` is the vector used in our DFS calls to store the way to the currently parsed node.\n\nIn our main function, we will then first of all populate `paths`, with a call to our `dfs` helper function.\n\nThis function takes 2 parameters, the currently parsed node `root` and:\n* updates `tmp` pushing `root` in;\n* checks if now `tmp` is either the first elements that would be pushed in paths or longer (ie: deeper) than the last inserted one, in which case it overwrites `paths` to just contain it;\n* alternatively checks if `tmp` is as long/deep as the last element in `paths`, in which case `tmp` gets appended to it;\n* calls itself recursively on the children branches, if any;\n* backtracks `tmp` popping `root` out.\n\nYou might save yourself some unnecessary checks removing `paths.empty()` from the first conditional, if you just push `{{root}}` into `paths` before calling `dfs` the first time, but I think it is not that much of a difference and I found more elegant to keep it in - just consider discussing this option if you are interviewing and want to show a keen eye for performances.\n\nOnce done, we loop as long as the last node in the first and the last path in `paths` are different (which also implies no looping at all in case we only had a single deepest path stored there, which is perfect), popping the last element out of both of them.\n\nFor example, with the provided sample input (`{3,5,1,6,2,0,8,null,null,7,4}`), we will end up having as deepest paths in `paths`:\n\n```cpp\n{3, 5, 2, 7}\n{3, 5, 2, 4}\n```\n\nTheir last element does not match, so we pop it out from both and get:`paths`:\n\n```cpp\n{3, 5, 2}\n{3, 5, 2}\n```\n\nNow their last element is the same, so that is our solution!\n\nOnce done, we can return the last element of the first (or of the last, it does not matter) path in `paths` :)\n\nThe code, who had decent time and somehow average memory consumption:\n\n```cpp\nclass Solution {\npublic:\n    // support variables\n    vector<vector<TreeNode*>> paths;\n    vector<TreeNode*> tmp;\n    // DFSing the deepest paths\n    void dfs(TreeNode* root) {\n        // updating tmp\n        tmp.push_back(root);\n        // if tmp is the new deepest, we overwrite paths\n        if (paths.empty() || tmp.size() > paths.back().size()) paths = {tmp};\n        // if tmp is as deep as the last element in paths, we add it\n        else if (tmp.size() == paths.back().size()) paths.push_back(tmp);\n        // recursive calls to the children, if any\n        if (root->left) dfs(root->left);\n        if (root->right) dfs(root->right);\n        // backtracking on tmp\n        tmp.pop_back();\n    }\n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        // extracting the longest paths\n        dfs(root);\n        // reducing the 2 extreme paths to the common node\n        while (paths.front().back() != paths.back().back()) paths.front().pop_back(), paths.back().pop_back();\n        return paths.front().back();\n    }\n};\n```\n\nThen I cam up with another alternative: to go recursively and take the depth of the left and right branch respectively, then compare them:\n* if they are equal, by definition we know that `root` is the one node that connects all the deepest ones;\n* otherwise, we call the function recursively on the deeper branch of the 2.\n\nThe code, that performs surprisingly very fast, despite recomputing over and over again the depth of several nodes (I try to optimise that part, but check below the code to know how it went):\n\n```cpp\nclass Solution {\npublic:\n    int getDepth(TreeNode *root) {\n        return root ? 1 + max(getDepth(root->left), getDepth(root->right)) : 0;\n    }\n\n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        int l = getDepth(root->left), r = getDepth(root->right);\n        return l == r ? root : subtreeWithAllDeepest(l > r ? root->left : root->right);\n    }\n};\n```\n\nI wanted to try a memoised version of it, but it does run significantly slower, to my surprise - not sure if searching through the map or the compiler being unable to properly work it with tail recursions is the culprit here.\n\nThe code of this disappointed experiment (which is of course burning some more memory for no gain):\n\n```cpp\nclass Solution {\npublic:\n    unordered_map<TreeNode*, int> depths;\n    int getMemoisedDepth(TreeNode *root) {\n        return root ? depths.find(root) != end(depths) ? depths[root] : depths[root] = 1 + max(getMemoisedDepth(root->left), getMemoisedDepth(root->right)) : 0;\n    }\n\n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        int l = getMemoisedDepth(root->left), r = getMemoisedDepth(root->right);\n        return l == r ? root : subtreeWithAllDeepest(l > r ? root->left : root->right);\n    }\n};\n```\n\nLast but not least, I took the idea of using Euler path from [here](https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/discuss/969164/Python-BFS-and-Euler-Path-with-picture) and tweaked it a bit to fit my idea (and optimise it as much as I could, of course).\n\nCheck the link above for a full, illustrated description of it, but the idea is to go with an in-order traversal (left-root-right) storing each element and the matching depth into 2 containers, that I declared respectively as `nodes` and `depths`, iterating though them with my usual pointer `pos`, that by the end of the process will also be the value of the number of nodes parsed (and thus the length of the array to actually be considered).\n\nFor example, running the first provided sample input (`{3,5,1,6,2,0,8,null,null,7,4}`) we will get:\n\n```cpp\n6 5 7 2 4 3 0 1 8 //nodes\n2 1 3 2 3 0 2 1 2 //depths\n```\n\nAs described in [rowe1227](https://leetcode.com/rowe1227)\'s solution, we now need to go and find the deeper nodes, then return the shallowest node between them.\n\nAnd I wanted to give myself an extra challenge: can we do it not just only in linear time, but in a single pass?\n\nTurns out there is a way!\n\nWe will need a few support variables:\n* `res` and `shallowestNode` are 2 `TreeNode` pointers;\n* `maxDepth` and `minDepth` are 2 others to store, as their name implies, the maximum depth found so far and the minimum depth found after each deepest node - I declared them conveniently at loop level, since we won\'t need them outside the loop - also note that we want to initialise the former as `-1`, in order to correctly register even the provided `root` as the deeper one, in the edge case of getting a single-noded tree as an input.\n\nThen we iterate through all the indexes `i` in the `0 - (pos - 1)` range and:\n* check if the current depth is the new maximum, in which case we:\n\t* we set both `maxDepth` and `minDepth` to the value of the current depth;\n\t* we set `res` to the value of the matching node;\n* check if instead the current depth is equal to the current maximim `maxDepth`, in which case we just set the node matching the shallowest depth found after the maximum as the new `res`;\n* check if instead the current depth is lesser than `minDepth`, in which case we:\n\t* update `minDepth` to its value;\n\t* update `shallowestNode` to the matching value in `nodes`.\n\nIt is not the most intuitive pattern ever, but you can check how it works: if you will find only a single node with the maximumm depth, than that is your answer; if you are going to find more than one, then the shallowest one you found in the middle is what you need to return.\n\nIt really works!\n\nAnd thus, once we are done, we can just return `res` :)\n\nThe code, which is rather fast and with average memory usage:\n\n```cpp\nclass Solution {\npublic:\n    // support variable - note: no need to initialise the arrays\n    int depths[500], pos = 0;\n    TreeNode *nodes[500];\n    void dfs(TreeNode* root, int depth = 0) {\n        // in-order traversal\n        if (root->left) dfs(root->left, depth + 1);\n        nodes[pos] = root, depths[pos++] = depth;\n        if (root->right) dfs(root->right, depth + 1);\n    }\n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        // support variables\n        TreeNode *res, *shallowestNode;\n        // populating the Euler path\n        dfs(root);\n        // finding the lowest depth and the highest node inside the first and last deeper node\n        for (int i = 0, maxDepth = -1, minDepth; i < pos; i++) {\n            // a deeper node is found\n            if (depths[i] > maxDepth) {\n                maxDepth = minDepth = depths[i];\n                res = nodes[i];\n            }\n            // another node as deep as maxDepth is found\n            else if (depths[i] == maxDepth) {\n                res = shallowestNode;\n            }\n            // updating the shallowest node found so far\n            else if (depths[i] < minDepth) {\n                minDepth = depths[i];\n                shallowestNode = nodes[i];\n            }\n        }\n        return res;\n    }\n};\n```
['Depth-First Search', 'Graph', 'C', 'C++']