[leetcode] 543. Diameter of Binary Tree

✅ 문제 - 두 정렬 리스트의 병합

 

이진트리에서 두 노드 간 가장 긴 경로의 길이를 출력하는 문제!

---

✅ 풀이

💡 Point

1. 1부터 시작해서 각 노드별로 좌, 우 서브트리를 dfs 방식으로 확인
2. 더이상 서브트리가 없을 경우 0 반환하고 부모 노드로 다시 올라감
3. 부모노드 기준 좌, 우 서브트리 확인하여 더 깊은 쪽 길이에 +1
4. 항상 최댓값을 반환하므로 가장 긴 길이를 출력할 수 있다.

 

 

출력 샘플 그림으로 그려보며 이해해 봤다.

1부터 시작하여 서브트리 순회를 각각 하는데, 

2로 내려가면 또 4, 5 서브트리가 있으니 더 이상 서브트리가 없을 때까지 dfs 탐색을 한다.

서브트리가 없으면 0을 반환하며 다시 부모 노드로 올라가는데 이때 좌 우 트리깊이 중 더 깊은 값에 +1을 해준다.

 

2를 예로 들자면,

4와 5는 더이상 서브트리가 없으므로 둘 다 0이라 return max(left_depth, right_depth) + 1 하면 ) 0+1 = 1이다

 

1일 때는 2에서 올라오는 값은 2이고 3에서 올라오는 값은 1이니까

둘 중에 더 큰 값인 2 + 1을 해서 최종 값이 3이 되는 것이다.

 

 

코드

# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        result = 0

        # 왼쪽, 오른쪽 서브트리 나누어 dfs 탐색하면서
        # 각각 depth 길이 구하고 더하기
        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal result

            # 빈 트리일때 0 반환
            if not node:
                return 0

            # 왼쪽트리, 오른쪽트리 나누어 dfs 탐색
            left_depth = dfs(node.left)
            right_depth = dfs(node.right)

            #두 길이 합치기
            current_length = left_depth + right_depth

            result = max(result, current_length)

            # 더 깊은 쪽 깊이 + 1
            return max(left_depth, right_depth) + 1

        dfs(root)
        return result