[LeetCode] 543. Diameter of Binary Tree (DFS)

목차

접근

Easy난이도라는데, 고민을 많이 꽤 했던 것 같다. Grind 75를 따라가면서, 릿코드 문제를 풀어보고 있는 도중에 접했다.

 

Binary Tree의 지름을 구하는 문제이다. 여기서 Diameter(지름)의 의미는 트리에 존재하는 두 노드간의 가장 긴 거리를 의미한다. root를 거칠수도, 거치지 않을 수도 있다.

 

처음 접근은 정말 단순하게 생각했던 것 같다. 그냥 root의 left, right의 가장 긴 깊이를 구해서 더하면 끝 아닌가? 생각했다. 왜냐하면 가장 긴 거리가 나오려면, 무조건 root 노드를 지나가야한다고 생각했기 때문이다.

근데 엄청난 예제가 등장했다...두둥

 

 이 트리는 root를 거치지 않고서, right노드의 하위노드간에서 diameter가 등장한다.(-1 -> -2)

그래서 하루정도 더 고민을 해봤다.

해결

결론은 생각보다 쉽게 낫다.  어차피 우리가 구하는건 노드간의 가장 긴 거리다. 근데 이 diameter의 등장이 root노드를 거쳐서 나오지 않을 수도 있다는 것. 즉, root에서만 diameter를 구하기 위해서 접근하지말고(left max_depth + right max_depth), 내부에서 재귀로 깊이를 구해나갈 때 max_distance를 업데이트 하면 최대 거리가 나오지 않을까 생각했다.

 

결론적으로 이 접근이 맞았고, 생각보다 싱겁게 통과했다.

 

코드

# 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:
        self.max_dia = 0
        def dfs(node):
            if node is None:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)

            self.max_dia = max(self.max_dia, left+right) # 현재 재귀상태의 left+right(diameter 계산)와 저장된 diameter의 max를 업데이트한다.
            return max(left, right) + 1 # left, right 중 가장 깊은 깊이로 업데이트

        
        dfs(root)
        return self.max_dia

 

 

 

잡설로, LeetCode는 처음 써보는데 너무 좋은 것 같다. discussion도 잘되어있고, 외국인들의 직설적인 얘기도 보면 재미있다. 또 틀린 예시를 주고, 이걸 바로 Case로 사용할 수 있는 것도 너무 좋은 것 같다.(백준이나 프로그래머스에서 Hidden Case 다 가려놓는거 진짜 이해 안된다. 공부하려고 플랫폼 사용하는건데, 테스트 보듯이 가려놓는 이유는 정말 이해 안간다.)

 

안좋은 점은, 플랫폼 내부에 코드 에디터 이쁘고, 잘 만들어놨으면서 자동완성 기능을 구독으로 판다... 왜...?

그렇다고 주어진 sample을 내 코드에디터에서 쓰려고 한다면, 입력틀이 정해진 일부 문제같은 경우엔 채점 코드를 내가 직접 다 작성해야한다.(딱 이런 문제, 입력은 리스트로 주어지는 것처럼 보여놓고, 실제로는 Binary Tree로 가공을 해야하는 것)

내 코드에디터에서 이런 공수를 들여서까지 채점을 하고싶진 않기에, 내부 에디터를 그냥 사용하는데 이건 정말 불편한 것 같다.

 

말 그대로 잡설이었다..,,

Kaggle AIMO 대회 참여하면서, 흥미롭게 읽은 Apple의 GSM-Symbolic 논문 후기도 조만간 완성해서 올려야지.. 총총.