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

difficulty: Medium

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

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

/**
 * 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);
    }
}