-
Notifications
You must be signed in to change notification settings - Fork 514
/
c.go
64 lines (61 loc) · 1.07 KB
/
c.go
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
package main
import . "github.com/EndlessCheng/codeforces-go/leetcode/testutil"
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pseudoPalindromicPaths(root *TreeNode) (ans int) {
cnt := [10]int{}
var f func(*TreeNode)
f = func(o *TreeNode) {
if o == nil {
return
}
v := o.Val
cnt[v]++
defer func() { cnt[v]-- }()
if o.Left == nil && o.Right == nil {
odd := 0
for _, c := range cnt {
if c&1 == 1 {
odd++
}
}
if odd <= 1 {
ans++
}
}
f(o.Left)
f(o.Right)
}
f(root)
return
}
// 复杂度与 o.Val 的范围无关的写法
func pseudoPalindromicPaths2(root *TreeNode) (ans int) {
has := map[int]bool{}
var f func(*TreeNode)
f = func(o *TreeNode) {
if o == nil {
return
}
if v := o.Val; has[v] {
delete(has, v)
defer func() { has[v] = true }()
} else {
has[v] = true
defer func() { delete(has, v) }()
}
if o.Left == nil && o.Right == nil && len(has) <= 1 {
ans++
}
f(o.Left)
f(o.Right)
}
f(root)
return
}