ARST打卡第163周[163/521]

发表于 2022-06-19 更新于 2022-06-20 分类于 ARST 阅读次数：

lc508出现次数最多的子树元素和 golangci-lint Linters Could not find nil pointer golangci-lint在vscode的使用，以及配置的一些探索

Algorithm

lc508出现次数最多的子树元素和

维护一个子树和的map次数，然后取最多次数的一个slice

dfs记忆搜索

结果写了60分钟，各种翻车…白板写新学的go，写得太菜了…，还是有错，快凌晨了，明天debug一下

难道是我map使用方式有问题？？？

map提出去又出现下面的问题…

输入：
[1]
输出：
[2]
预期结果：
[1]

第二天用本地go环境去跑，发现跑出来的结果和LeetCode跑出来的结果不一样，本地可以正确得到结果

查了一下，发现是LeetCode的golang不能用全局变量…所以改成引用传值，就过了…

教训: 下次还是要装一个本地golang环境，白板没法调试，不方便…反而会浪费更多宝贵的时间

// 输入：
// [1]
// 输出：
// []
// 预期结果：
// [1]

// var maxCnt = 0

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findFrequentTreeSum(root *TreeNode) (ans []int) {
	treeSum := make(map[int]int)
	// missing len argument to make([]int)
	// ans := make([]int)

	// [0,0,0,0,0,0,0,0,0,0]
	// ans := make([]int, 10)
	// ans := make([]int, 0)
	maxCnt := 0
	// cannot use dummyNode (type leetcode.TreeNode) as type *leetcode.TreeNode in argument to dfsGetSum
	// dummyNode := TreeNode{
	// dummyNode := &TreeNode{
	//     // unexpected =, expecting comma or }
	//     // Left = root
	//     Left: root,
	// }
	// dfsGetSum(treeSum, dummyNode, maxCnt)
	dfsGetSum(treeSum, root, &maxCnt)
	for k, v := range treeSum {
		if v == maxCnt {
			ans = append(ans, k)
		}
	}
	return
}

// maxCnt是传值！！！不会往上传！！！这里是错的
func dfsGetSum(treeSum map[int]int, root *TreeNode, maxCnt *int) int {
	// func dfsGetSum(treeSum map[int]int, root *TreeNode) int {
	// panic: runtime error: invalid memory address or nil pointer dereference
	// if nil == root.Left && nil == root.Right {
	//     treeSum[root.Val] += 1
	//     if treeSum[root.Val] > maxCnt {
	//         maxCnt = treeSum[root.Val]
	//     }
	//     return treeSum[root.Val] : 返回错了...
	// }
	if root == nil {
		return 0
	}

	nodeSum := root.Val + dfsGetSum(treeSum, root.Left, maxCnt) +
		dfsGetSum(treeSum, root.Right, maxCnt)
	treeSum[nodeSum] += 1
	if treeSum[nodeSum] > *maxCnt {
		*maxCnt = treeSum[nodeSum]
	}
	// return treeSum[nodeSum] : 返回错了...
	return nodeSum
}

题解写得比我优美，用了闭包

func findFrequentTreeSum(root *TreeNode) (ans []int) {
    cnt := map[int]int{}
    maxCnt := 0
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        sum := node.Val + dfs(node.Left) + dfs(node.Right)
        cnt[sum]++
        if cnt[sum] > maxCnt {
            maxCnt = cnt[sum]
        }
        return sum
    }
    dfs(root)

    for s, c := range cnt {
        if c == maxCnt {
            ans = append(ans, s)
        }
    }
    return
}
// 链接：https://leetcode.cn/problems/most-frequent-subtree-sum/solution/chu-xian-ci-shu-zui-duo-de-zi-shu-yuan-s-kdjc/