《零基础Go语言算法实战》【题目 5-1】按照给定条件构建二叉树
《零基础Go语言算法实战》
【题目 5-1】按照给定条件构建二叉树
给出一个含有不重复整数元素的数组，每个整数均大于 1。用这些整数来构建二叉树，
每个整数可以使用任意次数。其中，每个非叶子节点的值应等于它的两个子节点的值的乘积。
求满足条件的二叉树一共有多少个？返回的结果应模除以 10的9 次方+ 7。
【解答】
① 思路。
首先想到的是暴力解法，先排序，然后遍历所有节点，枚举两两乘积为第 3 个节点值的
组合，然后枚举这些组合并构成树。这里在计数时要注意，左右子树如果不是对称的，则将
左右子树相互对调又是一组解。
② Go 语言实现。
package main
import (
"fmt"
"sort"
)
const mod = 1e9 + 7
func countBinaryTrees(arr []int) int {
dp := make(map[int]int)
sort.Ints(arr)
for i, curNum := range arr {
for j := 0; j < i; j++ {
factor := arr[j]
quotient, remainder := curNum/factor, curNum%factor
if remainder == 0 {
dp[curNum] += dp[factor] * dp[quotient]
}
}
dp[curNum]++
}
totalCount := 0
for _, count := range dp {
totalCount += count
}
return totalCount % mod
}
func main() {
arr := []int{1, 6, 8, 99, 88}
res := countBinaryTrees(arr)
fmt.Println(res)
}