#1123
Lowest Common Ancestor of Deepest Leaves
pupil · 480 · lc medium +27 · verified · 79.4% accepted · 2,661 likes · top 91%
Description
Given the root of a binary tree, return the lowest common ancestor of all its deepest leaves.
Recall:
- A leaf has no children.
- The root is at depth 0; children of a depth-d node are at depth d + 1.
- The LCA of a set S is the deepest node A such that every node in S is in A's subtree.
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.
Code
1
2
3
4
5
6
7
8
9