Tree: 543. Diameter of Binary Tree ★

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