Lowest Common Ancestor of Deepest Leaves

LeetCode Q 1123 - Lowest Common Ancestor of Deepest Leaves

Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.

Example 1: Input: root = [1,2,3] ; Output: [1,2,3]
Explanation: The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1. The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".
Example 2: Input: root = [1,2,3,4] ; Output: [4]
Example 3: Input: root = [1,2,3,4,5] ; Output: [2,4,5]

Constraints:

• The given tree will have between 1 and 1000 nodes.
• Each node of the tree will have a distinct value between 1 and 1000.

Solution: DFS

Code:

public TreeNode lcaDeepestLeaves(TreeNode root) {
  return dfs(root, depth(root));
}

private int depth(TreeNode n) {
  if (n == null) return 0;
  return Math.max(depth(n.left), depth(n.right)) + 1;
}

private TreeNode dfs(TreeNode root, int dep) {
  if (root == null || dep == 1) return root;

  TreeNode l = dfs(root.left, dep - 1);
  TreeNode r = dfs(root.right, dep - 1);

  if (l == null) return r;
  if (r == null) return l;

  return root;
}