job 인터뷰/코테(Matroid) 준비

Tree: 543. Diameter of Binary Tree ★

hyunkookim 2025. 1. 16. 15:57

543. Diameter of Binary Tree

 

트리의 Diameter 즉, 지름을 구하려면,

  • 어떤 노드를 기준으로, 좌측 최장 길이+오른쪽 최장 길이..
  • 꼭. 이 노드가 root 가 아닐 수도 있음: The path does not necessarily have to pass through the root.

위 의 경우, 노드 3을 기준으로, 왼쪽 2, 오른쪽 2... 그래서 diameter 는 2+2=4 임

 

따라서,

전역 변수 max_length 만들고, 

모든 노드를 탐색하면서, 왼쪽+오른쪽 길이, 즉, max_lengh를 계속 업데이트 해야함. 

모든 노드 탐색시, dfs,,,로

 

# 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:
        # diameter: 지름, path 의 가장 긴 길이
        # 즉, 루트를 기준으로 왼쪽으로 제일 긴 깊이 + 오른쪽 제일 긴 깊이
        # root 가 0로..
        # bfs -> 큐
        if not root:
            return 0

        def getDepth(node):
            if not node:
                return 0

            q = deque([node])
            depth = 0
            while q:
                for _ in range(len(q)):
                    n = q.popleft()
                    if n.left:
                        q.append(n.left)
                    if n.right:
                        q.append(n.right)
                depth+=1
            return depth

        max_len = [0]

        def dfs(node):
            if not node:
                return 

            dfs(node.left)
            left_length = getDepth(node.left)
            right_length = getDepth(node.right)
            max_len[0] = max(max_len[0], left_length+right_length)
            dfs(node.right)

        dfs(root)
        return max_len[0]

 

문제점

  1. getDepth를 DFS 안에서 반복적으로 호출:
    • 각 노드에서 getDepth를 호출하여 서브트리 깊이를 계산하므로, 동일한 서브트리를 여러 번 탐색하게 됩니다.
    • 이는 시간 복잡도를 증가시키며, 트리 크기가 클수록 성능 저하를 유발합니다.
  2. DFS와 BFS 혼용:
    • 현재 코드에서는 DFS로 트리를 순회하면서 BFS로 깊이를 계산하는 구조인데, 트리 문제에서 일반적으로 하나의 탐색 방식을 일관되게 사용하는 것이 더 효율적입니다.

개선 방안

  1. DFS로 깊이 계산과 지름 갱신을 한 번에 수행:
    • getDepth 함수 없이, DFS 탐색 중에 왼쪽/오른쪽 깊이를 계산하고 이를 기반으로 지름을 업데이트할 수 있습니다.
    • 이 방식은 각 노드를 한 번씩만 방문하므로 시간 복잡도는 **O(N)**입니다.
  2. max_len을 전역 변수로 사용:
    • DFS 중에서 전역 변수로 지름을 업데이트하면 추가적인 BFS 호출 없이 최대 지름을 계산할 수 있습니다.
# 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:
        # diameter: 지름, path 의 가장 긴 길이
        # 즉, 루트를 기준으로 왼쪽으로 제일 긴 깊이 + 오른쪽 제일 긴 깊이
        # root 가 0로..
        # bfs -> 큐
        if not root:
            return 0

        # 최대 지름을 저장할 변수
        max_len = [0]

        def dfs(node):
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)
            max_len[0] = max(max_len[0], left+right) # 지금은 left+right
            return max(left,right)+1 # 가장 긴 길이 리턴, +1은 현재 노드 포함

        dfs(root)
        return max_len[0]

 

 

https://youtu.be/bkxqA8Rfv04?si=M-l4av7h8npzxKgU

 

 

📘 영어 원문 + 📗 한글 해석

Given the root of a binary tree, return the length of the diameter of the tree.
📗 이진 트리의 루트가 주어졌을 때, 그 트리의 지름(diameter)의 길이를 반환하세요.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree.
📗 이진 트리의 지름은 트리 안의 두 노드 사이에서 가장 긴 경로의 길이입니다.
=> root 를 지나가지 않을수도 있음

This path may or may not pass through the root.
📗 이 경로는 루트를 지나갈 수도 있고, 지나가지 않을 수도 있습니다.

The length of a path between two nodes is represented by the number of edges between them.
📗 두 노드 사이의 경로의 길이는, 그들을 연결하는 간선(edge)의 개수로 표현됩니다.

 

이진 트리에서 깊이(depth)를 정의할 때,
보통은 루트에서 리프까지 도달하는 노드 수를 기준으로 합니다.

✅ 깊이(depth)의 기준 정리

노드 종류 깊이 반환값 이유
None (존재하지 않는 노드) 0 노드가 없으므로 깊이 없음
리프 노드 (자식 없음) 1 자기 자신 하나만 있음
일반 노드 1 + max(왼쪽 깊이, 오른쪽 깊이) 자식 노드의 깊이 중 최대값에 1을 더함

예시 코드 (깊이 계산)

def maxDepth(node):
    if not node:        # 자식이 없는 경우 → None
        return 0
    return 1 + max(maxDepth(node.left), maxDepth(node.right))

🔍 트리 예시

        1
       /
      2
     /
    3
  • 노드 3: 리프 → 깊이 1
  • 노드 2: 왼쪽 깊이 1 → 자기 포함해서 깊이 2
  • 노드 1: 왼쪽 깊이 2 → 자기 포함해서 깊이 3
  • None 노드는 모두 깊이 0

🧠 요약

상황반환되는 깊이
None (리프의 자식) 0
리프 노드 1
일반 노드 1 + max(왼쪽, 오른쪽)

 

 

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 트리 전체에서 가장 긴 지름(노드 간 경로 길이)을 저장할 변수
        self.max_diameter = 0

        def dfs(node):
            # 현재 노드가 없으면 (즉, 리프의 자식인 None 노드라면) 깊이는 0
            if not node:
                return 0

            # 왼쪽 자식 노드의 최대 깊이 계산
            left = dfs(node.left)

            # 오른쪽 자식 노드의 최대 깊이 계산
            right = dfs(node.right)

            # 현재 노드를 루트로 할 때의 경로 길이 = 왼쪽 깊이 + 오른쪽 깊이
            # 즉, 이 노드를 중심으로 좌우 끝까지 가는 가장 긴 경로
            self.max_diameter = max(self.max_diameter, left + right)

            # 부모 노드로는 현재 노드에서 출발 가능한 가장 깊은 경로만 리턴
            # 현재 노드 포함해서 1 + max(왼쪽, 오른쪽 깊이)
            return 1 + max(left, right)

        # 루트부터 DFS 시작
        dfs(root)

        # 최종적으로 저장된 최대 지름 반환
        return self.max_diameter

 

🔍 요약 정리

  • left + right: 어떤 노드를 중심으로 양쪽으로 갈 수 있는 최대 거리 (지름 후보)
  • 1 + max(left, right): 현재 노드의 최대 깊이 (부모에게 줄 값)
  • self.max_diameter: 모든 노드 기준으로 계산한 지름 중 가장 큰 값 저장

좋아요! 그럼 [1,2,3,4,5] 트리를 기준으로 그림과 함께 지름이 어떻게 계산되는지 보여드릴게요.

🌳 트리 구조: [1,2,3,4,5]

        1
       / \
      2   3
     / \
    4   5

🔁 DFS 흐름 (후위 순회)

우리는 각 노드에서 left depth + right depth를 계산하고, 그 합이 최대인 값을 기록합니다.

1️⃣ 노드 4 방문

  • 왼쪽 없음 → left = 0
  • 오른쪽 없음 → right = 0
  • left + right = 0 → 지름 업데이트 없음
  • 리턴값: 1 + max(0, 0) = 1

2️⃣ 노드 5 방문

  • 동일하게 깊이 1 리턴

3️⃣ 노드 2 방문

  • 왼쪽 깊이: 1 (from 4)
  • 오른쪽 깊이: 1 (from 5)
  • left + right = 2 → max_diameter = 2로 갱신됨!
  • 리턴값: 1 + max(1, 1) = 2

4️⃣ 노드 3 방문

  • 자식 없음 → 리턴값 1

5️⃣ 루트 노드 1 방문

  • 왼쪽 깊이: 2 (from node 2)
  • 오른쪽 깊이: 1 (from node 3)
  • left + right = 3 → max_diameter = 3로 최종 갱신됨!
  • 리턴값: 1 + max(2, 1) = 3

✅ 최종 결과

  • 가장 긴 경로: [4 → 2 → 1 → 3] 또는 [5 → 2 → 1 → 3]
  • 지름(diameter): 3 (edge 수 기준)