[leetcode] 894. All Possible Full Binary Trees

Description

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.

Example 1:

Input: 7 Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,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],[0,0,0,0,0,null,null,0,0]] Explanation:

Note:

1 <= N <= 20

分析

题目的意思是：给定一个值，输出所有满足条件的完全二叉树。这道题的思路根以前做过的输出所有二叉树类似，就是在遍历过程中，先选定根结点的位置，然后向左向右进行递归拓展，求出所有的左二叉树，然后求出所有的右二叉树，最后两两进行组合就能得到最终的二叉树的组合。终止条件是当前的N为0，如果N为1，说明就只需要构造一个结点返回就行了。其他的按照我刚才说的递归+循环就行了。

代码

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def allPossibleFBT(self, N: int) -> List[TreeNode]: if(N%2==0): return [] if(N==1): return [TreeNode(0)] res=[] for L in range(1,N,2): R=N-1-L l_list=self.allPossibleFBT(L) r_list=self.allPossibleFBT(R) for l_item in l_list: for r_item in r_list: root=TreeNode(0) root.left=l_item root.right=r_item res.append(root) return res

参考文献

[LeetCode] Simple to Understand | Python Recursion