[LeetCode 543] 이진 트리의 직경

소요 시간  : 90m

문제 이해

이진 트리의 루트가 주어지면 트리 지름의 길이를 반환합니다.
이진 트리의 직경은 트리의 두 노드 사이에서 가장 긴 경로의 길이입니다.
이 경로는 루트를 통과할 수도 있고 통과하지 않을 수도 있습니다.
두 노드 사이의 경로 길이는 두 노드 사이의 간선 수로 표시됩니다.

이진 트리의 루트가 주어지면

트리 지름의 직경 : 트리의 두 노드 사이에서 가장 긴 경로의 길이

두 노드 사이의 경로 길이는 두 노드 사이의 간선 수로 표시된다.

일단 주어진 노드 구조를 보자.

class TreeNode:
	def __init__(self, val=0, left=None, right=None):
    	self.val = val
        self.left = left
        self.right = right

일반 노드 구조이다. 별다른 특징은 없다.

다음으로 입력과 출력 예시를 보자.

def diameterOfBinaryTree(self, root : Optional[TreeNode]) -> int:

입력으로 Optional[TreeNode]를 받고 있다.

Optional이란 ?
typing 모듈의 라이브러리로, None이 허용되는 함수의 매개 변수에 대한 타입을 명시할 때 유용하다고 합니다.

root는 None을 허용하면서 TreeNode를 요소로 가지는 리스트를 의미하는 것이다.

 

Ex 1.

입력 : root = [1,2,3,4,5]

출력 : 3

설명 : 4 → 2 → 1 → 3 또는 5 → 2 → 1 → 3 ("→"의 수)

 

문제 풀기

문제 아이디어 도출

끝에서 끝까지 개수를 더하면 될 것 같은데,,
1에서 4까지 2개 + 1에서 3까지 1개
일단 루트 노드를 지나가는 것이 가장 최대 값을 가질 것 같다.
루트 노드의 왼쪽 트리의 최대 값과 오른쪽 트리의 최대 값을 각각 구하여 총합에 포함 시키면 되겠다.
또, 왼쪽 트리의 루트 노드도 마찬가지 원리로 포함시킨다. 오른쪽 트리도 마찬가지다.
재귀적으로 풀 수 있을 듯하다.

첫 번째 시도

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        def countDepth(root: Optional[TreeNode]) -> int:
            if not root:
                return 0
            count = int()
            count += countDepth(root.left) + countDepth(root.right) + 1
            return count

        total = countDepth(root)
        return total

말단 노드의 경우를 고려하여, root가 없으면 0을 반환하였다.
또한, root 노드부터 내려가면서 count를 더하는 방식으로 구현하기 위해
root가 있는 경우, root.left와 root.right를 더하고 1을 더하는 방식을 생각해서 코드를 짰다.
예시를 생각했을 때,
2가 루트 노드가 됐을 경우 count는 2가 되어야 한다.
3,4,5가 루트 노드가 됐을 경우 count가 1이 되어야 한다.
조건문을 수정해야 겠다.

두 번째 시도

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        def countDepth(root: Optional[TreeNode]) -> int:
            if not root:
                return 0
            elif root and not root.left and not root.right:
                return 1

            count = int()
            count += countDepth(root.left) + countDepth(root.right)
            return count

        total = countDepth(root)
        return total

세 번째 시도

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        def countDepth(root: Optional[TreeNode],count: int) -> int:
            if root:
                if root.left or root.right:
                    count += 1
                    count += countDepth(root.left, count) + countDepth(root.right, count)
                    return count
                return 0
            return 0

        return countDepth(root, 0)

네 번째 시도

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def countDepth(root: Optional[TreeNode]) -> int:
            if root:
                if root.left or root.right:
                    return max(countDepth(root.left), countDepth(root.right))
                return 1
            return 0

        return countDepth(root)

 

더 이상 생각이 나지 않아 자료를 찾아봐야겠다.!

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:
        self.max_diameter = 0

        def depth(node):
            if not node:
                return 0
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            return max(left_depth, right_depth) + 1

        depth(root)
        return self.max_diameter

깊이의 최대 값을 left와, right를 비교하는 것에 더불어 현재 자신의 max_diameter까지 비교하는 것이 핵심인 것 같다.

배운 점

트리 파트는 다른 파트보다 쉽지 않은 것 같다. 더 많이 풀어봐야겠다.