首页 > itarticle > leetcode 894 all possible full binary trees

leetcode 894 all possible full binary trees

admin 1月 23, 2021 0

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 (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
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能