import
json
class
TreeNode:
def
__init__(
self
, x):
self
.val
=
x
self
.left
=
None
self
.right
=
None
class
Solution:
def
generateTrees(
self
, n):
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()