Leetcode 894 All Possible Full Binary Trees

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.

分析:

  1. 显然完全二叉树的节点个数必是奇数,故if N % 2 == 0: return []
  2. 我们定义cache[i]表示i个节点构造出的完全二叉树的所有可能
  3. 如果N = 1,显然只有一种情况
  4. 如果N = 3,显然也只有一种情况
  5. 如果N = 5,如果左孩子为cache[1],右孩子则为cache[3];如果左孩子为cache[3],右孩子为cache[1]
  6. 依此类推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def allPossibleFBT(self, N):
if N % 2 == 0: return []
cache = {}
# 只考虑奇数情况
for i in range(N+1)[1::2]:
if i == 1: # 初始化
cache[1] = [TreeNode(0)]
continue
cache[i] = []
# j 代表左孩子的数量
for j in range(i)[1::2]:
for lkid in cache[j]:
for rkid in cache[i-1-j]:
node = TreeNode(0)
node.left = lkid
node.right = rkid
cache[i].append(node)
return cache[N]

20 / 20 test cases passed.
difficulty: medium
Runtime: 136 ms