題目連結: https://leetcode.com/problems/all-possible-full-binary-trees/
參考解法:
https://www.youtube.com/watch?v=noVVstnQvyY
解法:
var map: [Int: [TreeNode]] = [:]
func allPossibleFBT(_ n: Int) -> [TreeNode?] {
if n % 2 == 0 { return [] }
else {
if let found = map[n] {
return found
}
var result = [TreeNode]()
if n == 1 {
result.append(TreeNode(0))
return [TreeNode(0)]
} else {
for i in 1 ... (n-1) {
let leftTree = allPossibleFBT(i)
let rightTree = allPossibleFBT(n-1-i)
for leftNode in leftTree {
for rightNode in rightTree {
let node = TreeNode(0)
node.left = leftNode
node.right = rightNode
result.append(node)
}
}
}
}
map[n] = result
return result
}
}