ARST打卡第169周[169/521]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

// 感觉这个题目和之前的一次面试题很像，就是bfs，但是面试时紧张记录了太多上下层的状态
func maxLevelSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	maxSum := math.MinInt64
	level := 1
	levelNodeCnt := 1
	queue := make([]*TreeNode, 0, 10)
	queue = append(queue, root)
	queueCnt := 1
	levelSum := 0
	ans := 1
	for queueCnt != 0 {
		head := queue[0]
		queue = queue[1:]
		queueCnt--
		levelNodeCnt--
		levelSum += head.Val
		if head.Left != nil {
			queue = append(queue, head.Left)
			queueCnt++
		}
		if head.Right != nil {
			queue = append(queue, head.Right)
			queueCnt++
		}
		if levelNodeCnt == 0 {
			if levelSum > maxSum {
				maxSum, ans = levelSum, level
			}
			level++
			// 这种没考虑null没有加入
			// levelNodeCnt = int(math.Pow(2, float64(level-1)))
			levelNodeCnt = len(queue)
			levelSum = 0
		}
	}

	return ans
}

// 答案比我的简洁多了
// bfs
func maxLevelSum_ans_Bfs(root *TreeNode) int {
	ans, maxSum := 1, root.Val
	q := []*TreeNode{root}
	for level := 1; len(q) > 0; level++ {
		tmp := q
		q = nil
		sum := 0
		for _, node := range tmp {
			sum += node.Val
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		if sum > maxSum {
			ans, maxSum = level, sum
		}
	}
	return ans
}

/*
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/solution/zui-da-ceng-nei-yuan-su-he-by-leetcode-s-2tm4/
*/
// dfs
func maxLevelSum_ans_Dfs(root *TreeNode) (ans int) {
	sum := []int{}
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, level int) {
		if level == len(sum) {
			sum = append(sum, node.Val)
		} else {
			sum[level] += node.Val
		}
		if node.Left != nil {
			dfs(node.Left, level+1)
		}
		if node.Right != nil {
			dfs(node.Right, level+1)
		}
	}
	dfs(root, 0)
	for i, s := range sum {
		if s > sum[ans] {
			ans = i
		}
	}
	return ans + 1 // 层号从 1 开始
}