894. 所有可能的满二叉树

本文主要是介绍894. 所有可能的满二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

894. 所有可能的满二叉树

原始题目链接：https://leetcode-cn.com/problems/all-possible-full-binary-trees/

满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

在这里插入图片描述

解题思路：

构造树的过程肯定是用递归的方法，递归就需要考虑结束条件和自身调用的问题。满二叉树的节点数目必须是奇数，因为要组合排列所有的满二叉树，所以可以从左子树的节点个数为1开始，每次增加一层就要增加2个节点才能满足满二叉的性质。

代码实现：

# 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 == 1:return [TreeNode(0)]# 偶数个节点不能满足满二叉树，返回空if n % 2 == 0:return []# 需要罗列所有的满二叉树的排列# 左子树的节点从1开始，且每次递增2# 因为满二叉要么节点数是1要么是3left_tree_num = 1# 剩下的右子树的节点数是减去根节点及左子树的节点right_tree_num = n - 2res = []while right_tree_num > 0:# 递归构造左子树left_tree = self.allPossibleFBT(left_tree_num)# 递归构造右子树right_tree = self.allPossibleFBT(right_tree_num)# 构造树的过程for i in range(len(left_tree)):for j in range(len(right_tree)):root = TreeNode(0)root.left = left_tree[i]root.right = right_tree[j]res.append(root)left_tree_num += 2right_tree_num -= 2return res