# 1123. Lowest Common Ancestor of Deepest Leaves¶

• Time: $O(h)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 struct T { TreeNode* lca; int depth; }; class Solution { public: TreeNode* lcaDeepestLeaves(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 class T { public TreeNode lca; public int depth; public T(TreeNode lca, int depth) { this.lca = lca; this.depth = depth; } }; class Solution { public TreeNode lcaDeepestLeaves(TreeNode root) { return dfs(root).lca; } private T dfs(TreeNode root) { if (root == null) return new T(null, 0); const T left = dfs(root.left); const T right = 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); } }