508. Most Frequent Subtree Sum

LeetCode medium оригинал: C# #array #csharp #hash-table #leetcode #math #medium #search #tree #two-pointers

LeetCode Static

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

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

Пример:

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

Output: [2,-3,4]

C# решение

сопоставлено/оригинал

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++ решение

auto-draft, проверить перед отправкой

#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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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
}

Algorithm

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

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

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

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.