Home Find Mode in Binary Search Tree
Post
Cancel

Find Mode in Binary Search Tree

Leetcode Problem

Find Mode in Binary Search Tree

이진 탐색 트리에서 가장 빈번하게 나오는 수들을 구하는 문제입니다. 가장 많이 나오는 수가 여러개일 경우 전부 구해야 합니다.

1
2
3
4
5
6
7
from collections import Counter
class Solution:
    def traverse(self, root: Optional[TreeNode]) -> List[int]:
        return [root.val] + self.traverse(root.left) + self.traverse(root.right) if root else []
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        counter = Counter(self.traverse(root))
        return [ x for x in counter if counter[x] == counter.most_common(1)[0][1] ]

preorder traversal로 tree 구조를 배열로 바꿉니다. 이후 collections의 counter 함수와 most_common 함수를 이용하여 가장 빈번한 수와 그 횟수를 구한 다음, 그 횟수와 일치하는 모든 수를 배열로 출력합니다.
하지만 이 풀이 방법은 성능이 좋지 않았습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        dict = {}
        max_ = -1
        
        def traverse(root):
            nonlocal max_
            if not root:
                return

            traverse(root.left)
            dict[root.val] = 1 + dict.get(root.val, 0)
            if max_ < dict[root.val]:
                max_ = max(max_, dict[root.val])
            
            traverse(root.right)
            
        traverse(root)
       
        lst2= []
        
        for key in dict.keys():
            if dict[key] == max_:
                lst2.append(key)
                
        return lst2

solution의 풀이는 순회 중에 가장 빈번한 수가 나오는 횟수를 미리 구하기 때문에 순회를 한번 더할 필요를 줄였습니다.





참고

This post is licensed under CC BY 4.0 by the author.