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