[Python] 纯文本查看 复制代码
import json
# Definition for a binary tree node.
class TreeNode: # 树的数据结构
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0: # 特殊情况处理
return []
if n == 1: # 特殊情况处理
return [[1]]
total = [x for x in range(1, n + 1)] # 首先生成点的集合
nodes = self.makeNode(total) # 生成树
result = list()
for node in nodes:
d = self.dumpTreeNode(node) # 导出结果树集合
tmp = list()
for i in range(9999): # 一层一层的将树输入到列表
if i not in d:
break
tmp.extend(d[i])
while tmp[-1] is None: # 将尾部的空节点删除
del tmp[-1]
result.append(tmp) # 将列表加入结果集
return result
def makeNode(self, item_set: list) -> list: # 生成树
if len(item_set) == 0: # 节点集没有一个点
return [None]
if len(item_set) == 1: # 节点集只有一个点
return [TreeNode(item_set[0])]
result = list()
if len(item_set) == 2: # 节点集只有两个点
if item_set[0] < item_set[1]:
node = TreeNode(item_set[0])
node.right = TreeNode(item_set[1])
result.append(node)
node = TreeNode(item_set[1])
node.left = TreeNode(item_set[0])
result.append(node)
else:
node = TreeNode(item_set[0])
node.left = TreeNode(item_set[1])
result.append(node)
node = TreeNode(item_set[1])
node.right = TreeNode(item_set[0])
result.append(node)
return result
for i in item_set: # 节点集有多个点
left = list()
right = list()
for j in item_set: # 遍历所有点,依次做根节点
if j == i:
continue
if j < i:
left.append(j)
continue
right.append(j)
ll = self.makeNode(left)
rr = self.makeNode(right)
for l_ in ll:
for r_ in rr: # 排列组合左右子树
node = TreeNode(i)
node.left = l_
if r_ is not None:
node.right = r_
result.append(node)
return result
def dumpTreeNode(self, node: TreeNode, level: int = 0) -> dict: # 导出树
result = dict()
result[level] = [node.val]
if isinstance(node.left, TreeNode):
r = self.dumpTreeNode(node.left, level + 1) # 递归导出子树
for k in r:
if k not in result:
result[k] = list()
result[k].extend(r[k])
else:
if level + 1 not in result:
result[level + 1] = list()
result[level + 1].append(node.left)
if isinstance(node.right, TreeNode):
r = self.dumpTreeNode(node.right, level + 1) # 递归导出子树
for k in r:
if k not in result:
result[k] = list()
result[k].extend(r[k])
else:
if level + 1 not in result:
result[level + 1] = list()
result[level + 1].append(node.right)
return result
def main(): # 测试函数主函数
test = [
'[]',
'[[1]]',
'[[1,null,2],[2,1]]',
'[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]',
'[[1,null,2,null,3,null,4],[1,null,2,null,4,3],[1,null,3,2,4],[1,null,4,2,null,null,3],[1,null,4,3,null,2],[2,1,3,null,null,null,4],[2,1,4,null,null,3],[3,1,4,null,2],[3,2,4,1],[4,1,null,null,2,null,3],[4,1,null,null,3,2],[4,2,null,1,3],[4,3,null,1,null,null,2],[4,3,null,2,null,1]]',
'[[1,null,2,null,3,null,4,null,5],[1,null,2,null,3,null,5,4],[1,null,2,null,4,3,5],[1,null,2,null,5,3,null,null,4],[1,null,2,null,5,4,null,3],[1,null,3,2,4,null,null,null,5],[1,null,3,2,5,null,null,4],[1,null,4,2,5,null,3],[1,null,4,3,5,2],[1,null,5,2,null,null,3,null,4],[1,null,5,2,null,null,4,3],[1,null,5,3,null,2,4],[1,null,5,4,null,2,null,null,3],[1,null,5,4,null,3,null,2],[2,1,3,null,null,null,4,null,5],[2,1,3,null,null,null,5,4],[2,1,4,null,null,3,5],[2,1,5,null,null,3,null,null,4],[2,1,5,null,null,4,null,3],[3,1,4,null,2,null,5],[3,1,5,null,2,4],[3,2,4,1,null,null,5],[3,2,5,1,null,4],[4,1,5,null,2,null,null,null,3],[4,1,5,null,3,null,null,2],[4,2,5,1,3],[4,3,5,1,null,null,null,null,2],[4,3,5,2,null,null,null,1],[5,1,null,null,2,null,3,null,4],[5,1,null,null,2,null,4,3],[5,1,null,null,3,2,4],[5,1,null,null,4,2,null,null,3],[5,1,null,null,4,3,null,2],[5,2,null,1,3,null,null,null,4],[5,2,null,1,4,null,null,3],[5,3,null,1,4,null,2],[5,3,null,2,4,1],[5,4,null,1,null,null,2,null,3],[5,4,null,1,null,null,3,2],[5,4,null,2,null,1,3],[5,4,null,3,null,1,null,null,2],[5,4,null,3,null,2,null,1]]'
]
for i in range(len(test)):
s = Solution()
r = s.generateTrees(i)
s = test[i]
r_ = json.loads(s)
print(len(r), len(r_))
for j, v in enumerate(r):
if v != r_[j]:
print(i, v == r_[j], v, r_[j])
if __name__ == '__main__':
main()