508. Most Frequent Subtree Sum

leetcode medium

#array#csharp#hash-table#leetcode#math#medium#search#tree#two-pointers

Task

Дано корень бинарного дерева, вернуть наиболее часто встречающуюся сумму поддерева. Если есть несколько таких значений, вернуть все значения с наибольшей частотой в любом порядке.

Сумма поддерева узла определяется как сумма всех значений узлов, образованных поддеревом, укорененным в этом узле (включая сам узел).

Пример:

Input: root = [5,2,-3]

Output: [2,-3,4]

C# solution

matched/original

using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    private Dictionary<int, int> sumFreq = new Dictionary<int, int>();
    private int maxFreq = 0;
    private int SubtreeSum(TreeNode root) {
        if (root == null) return 0;
        int leftSum = SubtreeSum(root.left);
        int rightSum = SubtreeSum(root.right);
        int currSum = root.val + leftSum + rightSum;
        if (sumFreq.ContainsKey(currSum)) {
            sumFreq[currSum]++;
        } else {
            sumFreq[currSum] = 1;
        }
        maxFreq = Math.Max(maxFreq, sumFreq[currSum]);
        return currSum;
    }
    public int[] FindFrequentTreeSum(TreeNode root) {
        SubtreeSum(root);
        List<int> result = new List<int>();
        foreach (var pair in sumFreq) {
            if (pair.Value == maxFreq) {
                result.Add(pair.Key);
            }
        }
        return result.ToArray();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    private unordered_map<int, int> sumFreq = new unordered_map<int, int>();
    private int maxFreq = 0;
    private int SubtreeSum(TreeNode root) {
        if (root == null) return 0;
        int leftSum = SubtreeSum(root.left);
        int rightSum = SubtreeSum(root.right);
        int currSum = root.val + leftSum + rightSum;
        if (sumFreq.count(currSum)) {
            sumFreq[currSum]++;
        } else {
            sumFreq[currSum] = 1;
        }
        maxFreq = max(maxFreq, sumFreq[currSum]);
        return currSum;
    }
    public vector<int>& FindFrequentTreeSum(TreeNode root) {
        SubtreeSum(root);
        List<int> result = new List<int>();
        foreach (var pair in sumFreq) {
            if (pair.Value == maxFreq) {
                result.push_back(pair.Key);
            }
        }
        return result.ToArray();
    }
}

Java solution

matched/original

class Solution {
    private HashMap<Integer, Integer> sumFreq = new HashMap<Integer, Integer>();
    private Integer maxFreq = 0;
    
    private int subtreeSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftSubtreeSum = subtreeSum(root.left);
        int rightSubtreeSum = subtreeSum(root.right);

        int currSum = root.val + leftSubtreeSum + rightSubtreeSum;
        
        sumFreq.put(currSum, sumFreq.getOrDefault(currSum, 0) + 1);
        maxFreq = Math.max(maxFreq, sumFreq.get(currSum));
        return currSum;
    }
    
    public int[] findFrequentTreeSum(TreeNode root) {
        subtreeSum(root);
        
        List<Integer> ansList = new ArrayList<Integer>(); 
        for (Map.Entry<Integer, Integer> mapElement : sumFreq.entrySet()) {
            Integer sum = mapElement.getKey();
            Integer freq = mapElement.getValue();
            
            if (freq == maxFreq) {
                ansList.add(sum);
            }
        }
        
        int maxFreqSums[] = new int[ansList.size()];
        for (int i = 0; i < ansList.size(); i++) {
            maxFreqSums[i] =  ansList.get(i).intValue();
        }
        
        return maxFreqSums;
    }
}

JavaScript solution

matched/original

var findFrequentTreeSum = function(root) {
    const sumFreq = new Map();
    let maxFreq = 0;

    const subtreeSum = (node) => {
        if (!node) return 0;
        const leftSum = subtreeSum(node.left);
        const rightSum = subtreeSum(node.right);
        const currSum = node.val + leftSum + rightSum;
        sumFreq.set(currSum, (sumFreq.get(currSum) || 0) + 1);
        maxFreq = Math.max(maxFreq, sumFreq.get(currSum));
        return currSum;
    };

    subtreeSum(root);

    const result = [];
    for (const [sum, freq] of sumFreq.entries()) {
        if (freq === maxFreq) {
            result.push(sum);
        }
    }
    return result;
};

Python solution

matched/original

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

class Solution:
    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        from collections import defaultdict
        
        sumFreq = defaultdict(int)
        maxFreq = 0
        
        def subtreeSum(node):
            nonlocal maxFreq
            if not node:
                return 0
            leftSum = subtreeSum(node.left)
            rightSum = subtreeSum(node.right)
            currSum = node.val + leftSum + rightSum
            sumFreq[currSum] += 1
            maxFreq = max(maxFreq, sumFreq[currSum])
            return currSum
        
        subtreeSum(root)
        return [s for s in sumFreq if sumFreq[s] == maxFreq]

Go solution

matched/original

import "math"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func findFrequentTreeSum(root *TreeNode) []int {
    sumFreq := make(map[int]int)
    maxFreq := 0

    var subtreeSum func(node *TreeNode) int
    subtreeSum = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftSum := subtreeSum(node.Left)
        rightSum := subtreeSum(node.Right)
        currSum := node.Val + leftSum + rightSum
        sumFreq[currSum]++
        if sumFreq[currSum] > maxFreq {
            maxFreq = sumFreq[currSum]
        }
        return currSum
    }

    subtreeSum(root)
    var result []int
    for sum, freq := range sumFreq {
        if freq == maxFreq {
            result = append(result, sum)
        }
    }
    return result
}

Explanation

Algorithm

Инициализация переменных

Инициализируйте переменные sumFreq для хранения частоты всех сумм поддеревьев. Инициализируйте maxFreq для хранения максимальной частоты. Создайте массив maxFreqSums для хранения всех сумм поддеревьев, частота которых равна максимальной.

Обход дерева и вычисление сумм

Выполните обход дерева в порядке post-order. Используйте суммы поддеревьев левого и правого дочерних узлов для вычисления суммы текущего поддерева. Увеличьте частоту текущей суммы в sumFreq. Обновите maxFreq, если частота текущей суммы больше текущего maxFreq.

Сборка результата

Пройдитесь по sumFreq и добавьте все суммы с частотой, равной maxFreq, в массив maxFreqSums. Верните массив maxFreqSums.

😎