Link: https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/

Question

difficulty: mid
adj diff: 3

Given the root of a 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. 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 = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest leaf-nodes of the tree.
Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.

Example 2:

Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree, and it's the lca of itself.

Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.

Constraints:

	The number of nodes in the tree will be in the range [1, 1000].
	0 <= Node.val <= 1000
	The values of the nodes in the tree are unique.

Code

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
29
30
class Pair {
    int depth;
    TreeNode node;
}

public TreeNode lcaDeepestLeaves(TreeNode root) {
    Pair p = findDepth(root);
    return p.node;
}

private Pair findDepth(TreeNode node) {
    Pair ret =  new Pair();
    if (node == null) {
        ret.depth = 0;
        return ret;
    }
    Pair leftDepth = findDepth(node.left);
    Pair rightDepth = findDepth(node.right);
    if (leftDepth.depth < rightDepth.depth) {
        ret.depth = rightDepth.depth + 1;
        ret.node = rightDepth.node;
    } else if (leftDepth.depth > rightDepth.depth) {
        ret.depth = leftDepth.depth + 1;
        ret.node = leftDepth.node;
    } else {
        ret.depth = leftDepth.depth + 1;
        ret.node = node;
    }
    return ret;
}