[Python3] dfs O(N)
Algo \nTraverse the tree. At each node, compare the height of left subtree to the height of right subtree. \n1) if left == right, return node;\n2) if left > rig
Algo \nTraverse the tree. At each node, compare the height of left subtree to the height of right subtree. \n1) if left == right, return node;\n2) if left > right, move to left subtree;\n3) if left < right, move to right subtree. \n\nImplementation\n```\nclass Solution:\n    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n        \n        @lru_cache(None)\n        def fn(node):\n            """Return height of tree rooted at node."""\n            if not node: return 0\n            return 1 + max(fn(node.left), fn(node.right))\n        \n        node = root\n        while node: \n            left, right = fn(node.left), fn(node.right)\n            if left == right: return node\n            elif left > right: node = node.left\n            else: node = node.right \n```\n\nAnalysis\nTime complexity `O(N)`\nSpace complexity `O(N)`\n\nEdited on 12/13/2020\n```\nclass Solution:\n    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n        fn = lru_cache(None)(lambda x: 1 + max(fn(x.left), fn(x.right)) if x else 0)\n        \n        node = root\n        while node: \n            if fn(node.left) == fn(node.right): return node \n            elif fn(node.left) < fn(node.right): node = node.right\n            else: node = node.left\n        return node \n```
['Python3']