root of a binary tree, return the lowest common ancestor of its deepest leaves.
- 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
Sof nodes, is the node
Awith the largest depth such that every node in
Sis in the subtree with root
Note: This question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
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.
Input: root =  Output:  Explanation: The root is the deepest node in the tree, and it's the lca of itself.
Input: root = [0,1,3,null,2] Output:  Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.
- The number of nodes in the tree will be in the range
0 <= Node.val <= 1000
- The values of the nodes in the tree are unique.
Break the problem into two sub-problems. 1. Find leaves at the deepest level 2. Find the lowest common ancestor between the two nodes. We can use a breadth-first search to find the leaves at the deepest level. Once find the leaves are at the deepest level, use the helper function for finding the lowest common ancestor to get the final answer. Note that if there are more than two leaves at the deepest level, use the leftmost and rightmost one.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]: leaves = self.find_leaves(root) if not leaves: return root if len(leaves) < 2: return leaves return self.find_lca(root, leaves, leaves[-1]) def find_leaves(self, root): if not root: return None queue =  queue.append(root) results =  while queue: size = len(queue) level =  for i in range(size): node = queue.pop(0) level.append(node) if node.left: queue.append(node.left) if node.right: queue.append(node.right) results.append(level) return results[-1] def find_lca(self, root, p, q): if not root: return None if p == root or q == root: return root left = self.find_lca(root.left, p, q) right = self.find_lca(root.right, p, q) if left and right: return root if left: return left if right: return right return None
- Time Complexity: O(N).
- Space Complexity: O(N).