Description
https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
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 isd, the depth of each of its children isd + 1. - The lowest common ancestor of a set
Sof nodes, is the nodeAwith the largest depth such that every node inSis in the subtree with rootA.
Note: This question is the same as 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
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.
Explanation
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.
Python Solution
# 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[0]
return self.find_lca(root, leaves[0], 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).