가장 깊은 잎의 가장 낮은 공통 조상

이진 트리의 root가 주어지면 가장 깊은 잎의 가장 낮은 공통 조상을 반환합니다.

다음을 기억하십시오.

이진 트리의 노드는 자식이 없는 경우에만 리프입니다

.

트리 루트의 깊이는 0 입니다. 노드의 깊이가 d 인 경우 각 자식의 깊이는 d + 1 입니다.

노드 집합S의 가장 낮은 공통 조상은 깊이가 가장 큰 노드A이므로 S의 모든 노드는 루트A가 있는 하위 트리에 있습니다.

예 1:



입력: 루트 = [3,5,1,6,2,0,8,null,null,7,4]
출력: [2,7,4]
설명: 다이어그램에서 노란색으로 표시된 값이 2인 노드를 반환합니다.
파란색으로 표시된 노드는 트리의 가장 깊은 리프 노드입니다.
노드 6, 0, 8도 리프 노드이지만 깊이는 2이지만 노드 7과 4의 깊이는 3입니다.

예 2:

입력: 루트 = [1]
출력: [1]
설명: 루트는 트리에서 가장 깊은 노드이며 자체 LCA입니다.

예 3:

입력: 루트 = [0,1,3,null,2]
출력: [2]
설명: 트리에서 가장 깊은 리프 노드는 2이고 한 노드의 lca는 자신입니다.

제약:

트리의 노드 수는 [1, 1000] 범위에 있습니다.

0 <= Node.val <= 1000

트리의 노드 값이 고유합니다.

참고: 이 질문은 865: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/과 동일합니다.

해결책:

# 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 maxDepth(self, root):
        if root:
            a = 1 + self.maxDepth(root.left)
            b = 1 + self.maxDepth(root.right)
            return max(a, b)
        return -1

    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            left = self.maxDepth(root.left)
            right = self.maxDepth(root.right)
            if left > right:
                return self.lcaDeepestLeaves(root.left)
            elif right > left:
                return self.lcaDeepestLeaves(root.right)
            else:
                return root