Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
输出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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理