(LeetCode) Most Frequent Subtree Sum with Python

🔥 문제

Given the root of a tree, you are asked to find the most frequent subtree sum.

: 주어진 트리의 루트를 통해서, 가장 빈번한 서브트리의 합을 찾아야한다.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

: 노드의 하위 트리 합계는 해당 노드 (노드 자체 포함)에 뿌리를 둔 서브트리에 의해 형성된 모든 노드 값의 합계로 정의됩니다.

So what is the most frequent subtree sum value?

: 가장 빈번한 서브 트리 합계의 값은 몇인가?

If there is a tie, return all the values with the highest frequency in any order.

: 동률이 있을 때 순서에 상관없이 빈도가 가장 높은 값을 반환한다.

 

Examples 1
Input:

 

    5
 ↙   ↘
2       -3

 

return [2, -3, 4], since all the values happen only once, return all of them in any order.

: 다 한 번씩 일어났기 때문에, 순서에 상관없이 모든 값을 리턴한다.

 

Examples 2
Input:

 

    5
 ↙   ↘
2       -5

 

return [2], since 2 happens twice, however -5 only occur once.

: 2가 두번 발생했기 때문에, 2를 반환한다. (-5 는 한 번 일어남)

 

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

 

 

💯 Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def findFrequentTreeSum(self, root):
 
        # subtree_sum 의 {값 : 빈도} 를 보여줄 딕셔너리를 만든다.
        self.subtree_sum_dict = {};
 
        # 서브트리의 합 중에서 제일 많이 나타난 주기에 대한 초기값 (처음은 0으로 잡는다.)
        self.highest_frequency = 0
 
        # 서브트리에서 제일 많이 나타난 값을 기록한다.
        # 배열의 값으로 return 해야하기 때문에 초기값은 []
        self.highest_freq_sum = []
 
        # =======================================================
        def helper(node):
            # 노드가 없다면
            if not node:
                #노드가 없으면 아무것도 없는 트리이다.
                return 0
            # 노드가 있다면
            else:
                # 노드의 왼쪽 줄기의 합
                left_sum = helper(node.left)
                # 노드의 오른쪽 줄기의 합
                right_sum = helper(node.right)
 
                # 노드의 총합
                cur_sum = left_sum + node.val + right_sum
 
                # get(키, 기본값)
                # self.subtree_sum_dict 딕셔너리에서 cur_sum 이라는 키를 정의한다.
                # self.subtree_sum_dict.get(cur_sum,0) : cur_sum 키가 없으면 0을 반환 , cur_sum 의 value 값을 등록
                self.subtree_sum_dict[cur_sum] = self.subtree_sum_dict.get(cur_sum,0) + 1
 
                # 가장 빈번한 주기보다 다 더한 값의 주기가 더 많거나 같다면
                if self.subtree_sum_dict[cur_sum] >= self.highest_frequency:
                    if self.subtree_sum_dict[cur_sum] > self.highest_frequency:
                        # 가장 빈번한 주기보다 다 더한 값의 주기가 많다면
                        # self.highest_frequency 를 cur_sum의 주기로 바꾼다.
                        self.highest_frequency = self.subtree_sum_dict[cur_sum]
                        self.highest_freq_sum = []
 
                    # 가장 빈번한 주기와 다 더한 값의 주기가 같다면,
                    # 가장 빈번한 주기일 때 합을 업데이트한다. {cur_sum : cur_sum_frequecnt}
                    self.highest_freq_sum.append(cur_sum)
 
                # 가장 빈번한 주기보다 다 더한 값의 주기가 더 적다면
                return cur_sum
        # ======================================================
 
        helper(root)
        # 해당 코드의 결과값은 제일 빈번한 주기의 합을 [] 형태로 반환해야한다.
 
       print(self.subtree_sum_dict)
       print(self.highest_frequency)
       print(self.highest_freq_sum)
 
        return self.highest_freq_sum

 

🗂 저장소

github.com/JiHoon-JK/Algorithm/blob/main/LeetCode/Most%20Frequent%20Subtree%20Sum.py

JiHoon-JK/Algorithm