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