Open Zheaoli opened 2 years ago
package main
/*
* @lc app=leetcode.cn id=508 lang=golang
*
* [508] 出现次数最多的子树元素和
*/
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// @lc code=start
func findFrequentTreeSum(root *TreeNode) []int {
cache := make(map[int]int)
res := make([]int, 0)
var dfs func(node *TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return 0
}
sumNode := node.Val + dfs(node.Left) + dfs(node.Right)
cache[sumNode] += 1
return sumNode
}
dfs(root)
maxCount := 0
for _, count := range cache {
if count > maxCount {
maxCount = count
}
}
for sumNode, count := range cache {
if count == maxCount {
res = append(res, sumNode)
}
}
return res
}
// @lc code=end
微信id: 而我撑伞 来自 vscode 插件
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int max = 0;
public int[] findFrequentTreeSum(TreeNode root) {
dfs(root);
List<Integer> list = new ArrayList<>();
for (Integer key : map.keySet()){
if (map.get(key) == max)
list.add(key);
}
int[] res = new int[list.size()];
int i = 0;
for (Integer num : list)
res[i++] = num;
return res;
}
int dfs(TreeNode root) {
if (root == null)
return 0;
int sum = dfs(root.left) + dfs(root.right) + root.val;
map.put(sum, map.getOrDefault(sum, 0) + 1);
max = Math.max(max, map.get(sum));
return sum;
}
}
WeChat: Saraad
2022-06-19