LeetCode 1123. Lowest Common Ancestor of Deepest Leaves

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 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.

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).

Leave a Reply

Your email address will not be published.