951. Flip Equivalent Binary Trees
思路:
翻转后父点的两个子点不变
做两次BFS
第一次纪录tree1每个点的子点
第二次检查tree2是否相同
func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
if root1 == nil && root2 == nil {
return true
} else if root1 == nil || root2 == nil {
return false
}
rec := map[int][]int{}
queue1 := []*TreeNode{root1}
for len(queue1) > 0 {
n := len(queue1)
for i := 0; i < n; i++ {
node := queue1[0]
queue1 = queue1[1:]
if node.Left != nil {
queue1 = append(queue1, node.Left)
rec[node.Val] = append(rec[node.Val], node.Left.Val)
}
if node.Right != nil {
queue1 = append(queue1, node.Right)
rec[node.Val] = append(rec[node.Val], node.Right.Val)
}
}
}
queue2 := []*TreeNode{root2}
for len(queue2) > 0 {
n := len(queue2)
for i := 0; i < n; i++ {
node := queue2[0]
queue2 = queue2[1:]
if node.Left != nil && node.Right != nil {
if len(rec[node.Val]) != 2 || !check(rec[node.Val], node.Left.Val) || !check(rec[node.Val], node.Right.Val) {
return false
}
queue2 = append(queue2, node.Left, node.Right)
} else if node.Left != nil {
if len(rec[node.Val]) != 1 || !check(rec[node.Val], node.Left.Val) {
return false
}
queue2 = append(queue2, node.Left)
} else if node.Right != nil {
if len(rec[node.Val]) != 1 || !check(rec[node.Val], node.Right.Val) {
return false
}
queue2 = append(queue2, node.Right)
} else if len(rec[node.Val]) != 0 {
return false
}
}
}
return true
}
func check(rec []int, target int) bool {
for _, i := range rec {
if i == target {
return true
}
}
return false
}
=====
写完看别人的答案发现三五行就解决了
直接一次DFS比较就好
我这辈子就这样了