# 1123. Lowest-Common-Ancestor-of-Deepest-Leaves

difficulty: Medium

&#x20;section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }&#x20;

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

Recall that:

* The node of a binary tree is a *leaf* if and only if it has no children
* The *depth* of the root of the tree is 0, and if the depth of a node is `d`, the depth of each of its children is `d+1`.
* The *lowest common ancestor* of a set `S` of nodes is the node `A` with the largest depth such that every node in S is in the subtree with root `A`.

**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.

## Method One

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int deepest = 0;
    TreeNode lca;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        findDeepest(root, 0);
        return lca;
    }
    public int findDeepest(TreeNode root, int depth ) {
        deepest = Math.max(deepest, depth);
        if(root == null) {
            return depth;
        }
        int left = findDeepest(root.left, depth + 1);
        int right = findDeepest(root.right, depth + 1);
        if( left == deepest && right == deepest ) {
            lca = root;
        }
        return Math.max(left, right);
    }
}
```
