Posted on 2023-07-23 19:13
Uriel 阅读(16)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
输出n个节点构成的所有完全二叉树，DP，参考了Discussion -> https://leetcode.com/problems/all-possible-full-binary-trees/solutions/3803284/python3-solution/
1 #894
2 #Runtime: 148 ms (Beats 81.71%)
3 #Memory: 17 MB (Beats 80.49%)
4
5
6 # Definition for a binary tree node.
7 # class TreeNode(object):
8 # def __init__(self, val=0, left=None, right=None):
9 # self.val = val
10 # self.left = left
11 # self.right = right
12 class Solution(object):
13 def allPossibleFBT(self, n):
14 """
15 :type n: int
16 :rtype: List[TreeNode]
17 """
18 if n % 2 == 0:
19 return []
20 dp = [[] for _ in range(n + 1)]
21 dp[1] = [TreeNode(0)]
22 for i in range(3, n + 1):
23 for j in range(1, i):
24 l_tree = dp[j]
25 r_tree = dp[i - 1 - j]
26 for l_t in l_tree:
27 for r_t in r_tree:
28 root = TreeNode(0)
29 root.left = l_t
30 root.right = r_t
31 dp[i].append(root)
32 return dp[n]