[LeetCode] 508. Most Frequent Subtree Sum

😎풀이

1. 깊이우선탐색 실행
   1-1. 현재 노드와 좌 우측 노드의 합 계산
   1-2. 동일한 합을 갖는 Tree의 빈도 계산
   1-3. 최대 빈도 갱신
2. 모든 Tree 빈도 순회
   2-1. 최대 빈도와 동일한 Tree Sum 확인
   2-2. 정답 배열에 추가
3. 최대 빈도를 갖는 Subtree의 Sum 배열 형태로 반환

function findFrequentTreeSum(root: TreeNode | null): number[] {
    const frequent = new Map<number, number>()
    let maxFreq = 0
    function dfs(node: TreeNode | null) {
        if(!node) return 0
        const left = dfs(node.left)
        const right = dfs(node.right)
        const total = node.val + left + right
        const curFreq = (frequent.get(total) ?? 0) + 1
        frequent.set(total, curFreq)
        maxFreq = Math.max(maxFreq, curFreq)
        return total
    }
    dfs(root)
    const result = []
    for(const [key, value] of frequent) {
        if(value < maxFreq) continue
        result.push(key)
    }
    return result
};