[Swift]LeetCode894.所有可能的满二叉树|AllPossibleFullBinaryTrees

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10605621.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

Note:

1 <= N <= 20

满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

示例：

输入：7
输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
解释：

提示：

1 <= N <= 20

116ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var countToTrees: [Int: [TreeNode]] = [
16         1: [TreeNode(0)]
17     ]
18 
19     func allPossibleFBT(_ N: Int) -> [TreeNode?] {
20         if N % 2 == 0 || N < 0 {
21             return []
22         } else if let trees = countToTrees[N] {
23             return trees
24         }
25         
26         var fbts = [TreeNode]()
27         
28         let remaining = N - 1
29         var leftCount = 1
30         while leftCount < N - 1 {
31             let leftFbts = allPossibleFBT(leftCount)
32             let rightFbts = allPossibleFBT(remaining - leftCount)
33             
34             for lfbt in leftFbts {
35                 for rfbt in rightFbts {
36                     let root = TreeNode(0)
37                     root.left = lfbt
38                     root.right = rfbt
39                     fbts.append(root)
40                 }
41             }
42             
43             leftCount += 2
44         }
45         
46         countToTrees[N] = fbts
47         return fbts
48     }
49 }

120ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var dict: Dictionary<Int,[TreeNode]> = [:]
16     func allPossibleFBT(_ N: Int) -> [TreeNode?] {
17         if N % 2 == 0 {
18             return []
19         }
20         
21         return expand(N - 1)
22     }
23     
24     private func expand(_ N: Int) -> [TreeNode] {
25         var result: [TreeNode] = []
26         if N == 0 {
27             return [TreeNode(0)]
28         } else if N == 2 {
29             let newNode = TreeNode(0)
30             newNode.left = TreeNode(0)
31             newNode.right = TreeNode(0)
32             result.append(newNode)
33             return result
34         } else {
35             if let nodes = dict[N] {
36                 return nodes
37             }
38             for i in 0...(N - 2)/2 {
39                 let left = i * 2
40                 let right = (N - 2) - left
41                 let leftNodes = expand(left)
42                 let rightNodes = expand(right)
43                 for lNode in expand(left) {
44                     for rNode in expand(right) {
45                         let newNode = expand(2)[0]
46                         newNode.left = lNode
47                         newNode.right = rNode
48                         result.append(newNode)
49                     }
50                 }
51             }
52             dict[N] = result
53             return result
54         }
55     }
56 }

136ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func allPossibleFBT(_ N: Int) -> [TreeNode?] {
16     if N == 1 {
17         return [TreeNode(0)]
18     } else if N < 1 || N % 2 == 0 {
19         return []
20     }
21     
22     var arr: [TreeNode] = []
23     for i in stride(from: 1, to: N-1, by: 2) {
24         let lArr = allPossibleFBT(i)
25         let rArr = allPossibleFBT(N-i-1)
26         
27         for j in 0..<lArr.count {
28             for k in 0..<rArr.count {
29                 let t = TreeNode(0)
30                 t.left = lArr[j]
31                 t.right = rArr[k]
32                 arr.append(t)
33             }
34         }
35     }    
36     return arr
37     }
38 }

Runtime: 152 ms

Memory Usage: 23.9 MB

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var cache:[Int:[TreeNode?]] = [Int:[TreeNode?]]()
16     func allPossibleFBT(_ N: Int) -> [TreeNode?] {
17         var N = N
18         var res:[TreeNode?] = [TreeNode?]()
19         if N % 2==0 {return res}
20         if cache[N] != nil {return []}
21         if N == 1
22         {
23             res.append(TreeNode(0))
24             return res
25         }
26         N -= 1
27         for i in stride(from:1,to:N,by:2)
28         {
29             var left:[TreeNode?] = allPossibleFBT(i)
30             var right:[TreeNode?] = allPossibleFBT(N - i)
31             for nl in left
32             {
33                 for nr in right
34                 {
35                     var cur:TreeNode? = TreeNode(0)
36                     cur?.left = nl
37                     cur?.right = nr
38                     res.append(cur)
39                 }
40             }
41         }
42         cache[N] = res
43         return res
44     }
45 }