【Python】记录槽位法：Leetcode894.所有可能的真二叉树

描述

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

示例 1：

输入：n = 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]]

示例 2： 输入：n = 3 输出：[[0,0,0]]

思路

一开始看错返回类型了，以为是返回字符串，因此思路也受到了影响

大概就是字符串，或者说是一个栈，如同题目所描述的输出一样，表示一个二叉树。其可以添加进结点或者Null，同时记录“槽位”数量，当槽位不足时则返回，否则当结点数量满足要求时返回这个树的结果。由于一次必定添加两个结点或者Null，因此可以只添加一个值便可区分，然后再通过队列将层序形式的树结点串构造成对应的二叉树。 枚举有效的二叉树使用dfs。

代码 class Solution: def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]: #print(n) if(n%2 == 0): return [] tree = [] self.all_tree = [] self.n = n self.dfs(tree) return self.all_tree def dfs(self,tree,node_num = 1,remain_slot = 2): if(remain_slot <= 0): return if(node_num == self.n): self.all_tree.append(self.createTree(tree)) return tree.append(0) self.dfs(tree,node_num+2,remain_slot+2) tree.pop() tree.append(None) self.dfs(tree,node_num,remain_slot-2) tree.pop() @staticmethod def createTree(tree_arr): tree = TreeNode(0) node_q = deque() node_q.append(tree) for node in tree_arr: if(node == None): node_q.popleft() continue else: temp_node = node_q[0] temp_node.left = TreeNode(0) temp_node.right = TreeNode(0) node_q.append(temp_node.left) node_q.append(temp_node.right) node_q.popleft() return tree