赞
踩
满二叉树是一类二叉树,其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
输入:7
输出:
[
[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]
]
解释:
提示:1 <= N <= 20
显然 N N N为偶数不可能组成一个满二叉树。用递归来做,对于一个 N N N,递归 N N N的左子树和右子树节点数量,例如 N = 7 N=7 N=7,就分为三种组合 ( 1 , 5 ) , ( 3 , 3 ) , ( 5 , 1 ) (1,5),(3,3),(5,1) (1,5),(3,3),(5,1)。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def allPossibleFBT(self, N: int) -> List[TreeNode]: if N%2 == 0: return [] if N == 1: return [TreeNode(0)] res = [] for i in range(1, N, 2): lchild = self.allPossibleFBT(i) rchild = self.allPossibleFBT(N-i-1) for l in lchild: for r in rchild: root = TreeNode(0) root.left = l root.right = r res.append(root) return res
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。