# 865. Smallest Subtree with all the Deepest Nodes       • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 struct T { TreeNode* lca; int depth; }; class Solution { public: TreeNode* subtreeWithAllDeepest(TreeNode* root) { return dfs(root).lca; } private: T dfs(TreeNode* root) { if (root == nullptr) return {nullptr, 0}; const T left = dfs(root->left); const T right = dfs(root->right); if (left.depth > right.depth) return {left.lca, left.depth + 1}; if (left.depth < right.depth) return {right.lca, right.depth + 1}; return {root, left.depth + 1}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class T { public TreeNode lca; public int depth; public T(TreeNode lca, int depth) { this.lca = lca; this.depth = depth; } }; class Solution { public TreeNode subtreeWithAllDeepest(TreeNode root) { return dfs(root).lca; } private T dfs(TreeNode root) { if (root == null) return new T(null, 0); T l = dfs(root.left); T r = dfs(root.right); if (left.depth > right.depth) return new T(left.lca, left.depth + 1); if (left.depth < right.depth) return new T(right.lca, right.depth + 1); return new T(root, left.depth + 1); } }