This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
describe
Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.
Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.
A full binary tree is a binary tree where each node has exactly 0 or 2 children.
Example 1:
Input: n = 7 Output: [[0, 0, null, null, 0, 0, null, null, 0, 0] to [0, 0, null, null, 0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0, null, null, null, null, 0, 0] to [0, 0, 0, 0, null, null, 0, 0]]Copy the code
Example 2:
Input: n = 3
Output: [[0,0,0]]
Copy the code
Note:
1 <= n <= 20
Copy the code
parsing
According to the question, given an integer n, let us return to all possible full binary tree (requiring that all nodes have zero or two leaves of the tree), and all the values of the nodes is 0, will all possible full binary tree root into the list and return, the final result of the order of the binary tree can be arbitrary.
In fact, when it comes to tree type data structures, there’s a high probability that recursion is used, and this problem also uses recursion. In fact, as you can see by enumerating several columns, a full binary tree requires n to be a positive odd number, otherwise you just return an empty list, because an even number of nodes does not make a full binary tree.
If n is 0, it returns an empty list and if n is 1 it returns a root list with only one node of value 0 and if n is 3 it can only form one full binary tree and if n is 5 there are two full binary trees, The number of nodes in the left and right subtrees may be 1 on the left and 3 on the right, or 3 on the left and 1 on the right. If n is 7, five binary trees will appear. The number of nodes in the left and right subtrees may be 1 on the left and 5 on the right, or 5 on the left and 1 on the right, 3 on the left and 3 on the right, Returns the root node list of five trees directly… It can be seen from finding rules that trees in the resulting list need to arrange and combine nodes, which requires three layers of cycles. The first layer controls the number of nodes in the left subtree l, the second layer traverses L left root nodes, and the third layer traverses N-1-L right root nodes.
answer
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def allPossibleFBT(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n%2==0: return []
if n == 1: return [TreeNode(0)]
N = n - 1
res = []
for l in range(1, N, 2):
for left in self.allPossibleFBT(l):
for right in self.allPossibleFBT(N - l):
node = TreeNode(0)
node.left = left
node.right = right
res.append(node)
return res
Copy the code
The results
Given in Python online submissions for All Possible Full Binary Trees. Given in the Python online submissions for All Possible Full Binary Trees.Copy the code
parsing
Another solution is to see a big god on the official website of the solution, the use of dynamic planning, the idea is really not seconds, and from the results, speed and occupied memory have a great improvement, do not admire not ah.
answer
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def allPossibleFBT(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
dp = [[] for _ in range(n + 1)]
dp[1] = [TreeNode()]
for i in range(1, n + 1, 2):
for j in range(1, i, 2):
for tree1 in dp[j]:
for tree2 in dp[i - j - 1]:
dp[i].append(TreeNode(0, tree1, tree2))
return dp[-1]
Copy the code
The results
Given in the Python online submissions for All Possible Full Binary Trees. Given in the Python online submissions for All Possible Full Binary Trees.Copy the code
Original link: leetcode.com/problems/al…
Your support is my biggest motivation