題目連結: https://leetcode.com/problems/all-possible-full-binary-trees/

參考解法:

https://www.youtube.com/watch?v=noVVstnQvyY

https://leetcode.com/problems/all-possible-full-binary-trees/discuss/813705/Swift-100-faster-than-all-swift-online-submissions

解法:

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
    }
}