Python two pass beats 99%
The idea is to compute the depth and the parent of each vertex in the tree. Then, find the deepest nodes in the tree and climb up starting from them until we re
The idea is to compute the depth and the parent of each vertex in the tree. Then, find the deepest nodes in the tree and climb up starting from them until we reach a common ancestor. I use dfs to compute the depths and parents, and then perform the climbing using them.\n\n```python\nclass Solution:\n    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n        parent, depth = {root: None}, {root: 0}\n        def dfs(node):\n            if node.right:\n                parent[node.right] = node\n                depth[node.right] = depth[node] + 1\n                dfs(node.right)\n            if node.left:\n                parent[node.left] = node\n                depth[node.left] = depth[node] + 1\n                dfs(node.left)\n        dfs(root)\n        \n        max_depth = max(depth.values())\n        deepest_nodes = set(node for node in parent.keys() if depth[node] == max_depth)\n        while len(deepest_nodes) > 1:\n            deepest_nodes = set(parent[node] for node in deepest_nodes)\n        \n        return deepest_nodes.pop()\n```
['Depth-First Search', 'Python', 'Python3']