1123. Lowest Common Ancestor of Deepest Leaves

Problem Statement

link: LeetCode.cn LeetCode 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.

Example:

Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4]

Input: root = [1] Output: [1]

Input: root = [0,1,3,null,2] Output: [2]

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.

Solution Approach

The solution finds the lowest common ancestor of the deepest leaves by recursively determining the depth of each subtree and selecting the node where both subtrees reach the same maximum depth.

Algorithm

1. Recursively traverse the tree to calculate the depth of each subtree.
2. Compare the depths of the left and right subtrees to identify where the deepest leaves are located.
3. The lowest common ancestor is the node where both subtrees have the same maximum depth.

Implement

    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]:
        def find(root):
            if not root:
                return 0, None
            d1, p1 = find(root.left)
            d2, p2 = find(root.right)

            if d1 > d2:
                return d1 + 1, p1
            if d1 < d2:
                return d2 + 1, p2
            return d1 + 1, root
        
        return find(root)[1]

    
    

Twitter  facebook  Email