[C++/Java/Python] One Pass
Explanatoin\nWrite a sub function deep(TreeNode root).\nReturn a pair(int depth, TreeNode subtreeWithAllDeepest)\n\nIn sub function deep(TreeNode root):\n\nif r
# Explanatoin\nWrite a sub function `deep(TreeNode root)`.\nReturn a `pair(int depth, TreeNode subtreeWithAllDeepest)`\n\nIn sub function `deep(TreeNode root)`:\n\n**if root == null**,\nreturn pair(0, null)\n\n**if left depth == right depth**,\ndeepest nodes both in the left and right subtree,\nreturn pair (left.depth + 1, root)\n\n**if left depth > right depth**,\ndeepest nodes only in the left subtree,\nreturn pair (left.depth + 1, left subtree)\n\n**if left depth < right depth**,\ndeepest nodes only in the right subtree,\nreturn pair (right.depth + 1, right subtree)\n<br>\n\n# Complexity\nTime `O(N)`\nSpace `O(height)`\n\n**C++**\n```cpp\n    TreeNode* subtreeWithAllDeepest(TreeNode* root) {\n        return deep(root).second;\n    }\n\n    pair<int, TreeNode*> deep(TreeNode* root) {\n        if (!root) return {0, NULL};\n        pair<int, TreeNode*> l = deep(root->left), r = deep(root->right);\n\n        int d1 = l.first, d2 = r.first;\n        return {max(d1, d2) + 1, d1 == d2 ? root : d1 > d2 ? l.second : r.second};\n    }\n```\n\n**Java**\n```java\n    public TreeNode subtreeWithAllDeepest(TreeNode root) {\n        return deep(root).getValue();\n    }\n\n    public Pair<Integer, TreeNode> deep(TreeNode root) {\n        if (root == null) return new Pair(0, null);\n        Pair<Integer, TreeNode> l = deep(root.left), r = deep(root.right);\n\n        int d1 = l.getKey(), d2 = r.getKey();\n        return new Pair(Math.max(d1, d2) + 1, d1 == d2 ? root : d1 > d2 ? l.getValue() : r.getValue());\n    }\n```\n**Python**\n```py\n    def subtreeWithAllDeepest(self, root):\n        def deep(root):\n            if not root: return 0, None\n            l, r = deep(root.left), deep(root.right)\n            if l[0] > r[0]: return l[0] + 1, l[1]\n            elif l[0] < r[0]: return r[0] + 1, r[1]\n            else: return l[0] + 1, root\n        return deep(root)[1]\n```\n
[]