1123. Lowest Common Ancestor of Deepest Leaves

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]

分析：

 1     class Pair {
 2         TreeNode node;
 3         int d;
 4         Pair(TreeNode node, int d) {
 5             this.node = node;
 6             this.d = d;
 7         }
 8     }
 9     public TreeNode lcaDeepestLeaves(TreeNode root) {
10         Pair p = getLca(root, 0);
11         return p.node;
12     }
13     private Pair getLca(TreeNode root, int d) {
14         if (root == null) return new Pair(null, d);
15         Pair l = getLca(root.left, d + 1);
16         Pair r = getLca(root.right, d + 1);
17         if (l.d == r.d) {
18             return new Pair(root, l.d);
19         } else {
20             return  l.d > r.d ? l : r;
21         }
22     }

1123. Lowest Common Ancestor of Deepest Leaves

原文：https://www.cnblogs.com/beiyeqingteng/p/12434355.html