[LeetCode]

 

 

 

작성 코드

 

접근 방법

 

1. 첫번째 루트 노드의 왼쪽 노드 중 최대 깊이 + 오른쪽 노드 중 최대 깊이 return

 

# Definition for a binary tree node.
import collections
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:
        
        if not root:
            return 0
        
        if not root.left:
            depth_left = 0
        else:
            deque_left = collections.deque([root.left])
            depth_left = 0
            while deque_left:
                depth_left += 1
                for _ in range(len(deque_left)):
                    cur_root = deque_left.popleft()
                    if cur_root.left:
                        deque_left.append(cur_root.left)
                    if cur_root.right:
                        deque_left.append(cur_root.right)
                   
        if not root.right:
            depth_right = 0
        else:
            deque_right = collections.deque([root.right])
            depth_right = 0
            while deque_right:
                depth_right += 1
                for _ in range(len(deque_right)):
                    cur_root = deque_right.popleft()
                    if cur_root.left:
                        deque_right.append(cur_root.left)
                    if cur_root.right:
                        deque_right.append(cur_root.right)
        return depth_left + depth_right

 

 

• 비슷한 코드를 좌, 우 적어야 하는 번거로움
• 왼쪽에만 노드들이 있을 때 / 한 방향에서 깊이가 큰 노드 묶음이 여러개 일때 해결 불가

 

 

이상 코드

 

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    longest: int = 0

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(node: TreeNode) -> int:
            if not node:
                return -1
            # 왼쪽, 오른쪽 각각 리프 노드까지 탐색
            left = dfs(node.left)
            right = dfs(node.right)

            # 가장 긴 경로
            self.longest = max(self.longest, left + right + 2)
            # 상태값
            return max(left, right) + 1

        dfs(root)
        return self.longest