543. Diameter of Binary Tree ☆☆★★ Diameter 정의, 리턴값 주의!

543. Diameter of Binary Tree

 

이 문제 Diameter of Binary Tree는 트리에서 두 노드 사이의 **가장 긴 경로의 길이(엣지 수)**를 구하는 문제입니다.

❗️Diameter에는 **노드 수가 아니라 엣지 수(edge count)**가 포함됩니다.

즉, **노드는 포함되지 않고, 그 사이의 연결선(엣지)**만 세는 거예요.

 

Diameter = 엣지 수 = 노드수 -1

---

📌 예시: root = [1,2,3,4,5]

이 트리 구조는 이렇게 생겼어요:

      1
     / \
    2   3
   / \
  4   5

가장 긴 경로는 4 -> 2 -> 1 -> 3 또는 5 -> 2 -> 1 -> 3

• 이 경로의 노드 수는 4개지만,
• 엣지 수 = 3개입니다 (4-2, 2-1, 1-3)

그래서 diameter = 3

---

✅ 요약:

• diameter = 가장 긴 경로의 엣지(edge) 수
• 노드 수로 계산하면 안 돼요!
• DFS 함수에서 left + right라고 했던 이유도 "엣지 수 계산"을 위한 것이에요.

---

🔍 핵심 개념:

• "Diameter"는 두 노드 사이의 가장 긴 경로의 edge 개수를 의미합니다.
• 이 경로는 반드시 root를 지나지 않아도 됩니다.
• 한 노드에서 시작해서 왼쪽 서브트리에서 가장 깊은 노드와 오른쪽 서브트리에서 가장 깊은 노드까지의 경로가 될 수 있어요.

---

✅ 접근 방식 (DFS + Post-order traversal):

1. 각 노드에서 왼쪽, 오른쪽 서브트리의 최대 깊이를 구함.
2. 그 깊이의 합이 현재 노드를 지나는 경로 중 가장 긴 경로가 될 수 있음.
3. 이때마다 최대값을 업데이트.
4. 전체 순회가 끝나면 최대값을 리턴.

---

✅ 코드 (Python):

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            
            """
            diameter = 에지 수 = 노드수 - 1, 그래서 현재노드 포함X
            그러나, 높이 계산시에는 현재노드 포함해야 함
            """
            
            # 현재 노드를 지나는 경로의 길이는 left + right            
            self.max_diameter = max(self.max_diameter, left + right)
            
            # 하위 노드로 전달할 높이 정보
            return 1 + max(left, right)
        
        dfs(root)
        return self.max_diameter

---

📌 시간 & 공간 복잡도:

• 시간복잡도: O(N)
  (모든 노드를 한 번씩 방문)
• 공간복잡도: O(H)
  (재귀 콜스택, H는 트리의 높이)

# 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 즉..에지 개수.. 노드개수 - 1 해야함
        self.maxDiameter = 0
        def dfs(node):
            if not node: # 끝이면
                return 0
            if not node.left and not node.right: 
                return 1 # 리프노트이면

            leftN = dfs(node.left)
            rightN = dfs(node.right)
            self.maxDiameter = max(self.maxDiameter, leftN+rightN)

            return 1+max(leftN, rightN) # 높이를 리턴해야하므로, 나포함(+1) 해서 두개 자식중 최대값

        dfs(root)
        return self.maxDiameter

---

2번째 내 풀이

# 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 of a binary tree is the length of the longest path between any two nodes in a tree. 
        => 가장 긴 이진 트리의 지름, 두 노드 사이의 거리 
        This path may or may not pass through the root.
        => root 를 지나지 않을 수 있음 => 모든 노드 검색해야 함
        """

        self.longest = 0
        def dfs(node):
            if not node:
                return 0
            if not node.left and not node.right: # 리프노드면
                return 1

            left = dfs(node.left)
            right = dfs(node.right)
            self.longest = max(self.longest, left+right+1) # 1은 현재 노드 포함

            return max(left, right)+1  # 1은 현재 노드 포함

        dfs(root)
        return self.longest

 

핵심은 문제에서 말하는 "지름(diameter)"의 정의입니다.

---

📌 문제 정의 다시 보기:

The diameter of a binary tree is the length of the longest path between any two nodes.
The length of a path is the number of edges between the two nodes.

---

⚠️ 여기서 중요한 포인트:

• 노드 개수가 아니라, X
• **엣지(간선)**의 개수를 세야 한다는 것!: 노드 수 -1

# 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 of a binary tree is the length of the longest path between any two nodes in a tree. 
        => 가장 긴 이진 트리의 지름, 두 노드 사이의 거리 
        This path may or may not pass through the root.
        => root 를 지나지 않을 수 있음 => 모든 노드 검색해야 함
        """

        self.longest = 0
        def dfs(node):
            if not node:
                return 0
            if not node.left and not node.right: # 리프노드면
                return 1

            left = dfs(node.left)
            right = dfs(node.right)
            """
            # 노드 개수 left+right+1: 1은 현재 노드 포함
            # 간선 개수 = 노드 개수 -1 = left+right
            """
            self.longest = max(self.longest, left+right) 

            return max(left, right)+1  # 1은 현재 노드 포함

        dfs(root)
        return self.longest