[笔记]算法学习:不同的二叉搜索树 II
本帖最后由 wushaominkk 于 2018-11-18 15:53 编辑题目:
解题要点:1 树类型的算法,一般都可以用递归来解决,因此首先考虑递归2 接着,要考虑如何生成树3 最后考虑如何输出树具体内容看下面代码注释import json
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
"""
if n == 0:# 特殊情况处理
return []
if n == 1:# 特殊情况处理
return []
total = # 首先生成点的集合
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)
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
if len(item_set) == 1:# 节点集只有一个点
return )]
result = list()
if len(item_set) == 2:# 节点集只有两个点
if item_set < item_set:
node = TreeNode(item_set)
node.right = TreeNode(item_set)
result.append(node)
node = TreeNode(item_set)
node.left = TreeNode(item_set)
result.append(node)
else:
node = TreeNode(item_set)
node.left = TreeNode(item_set)
result.append(node)
node = TreeNode(item_set)
node.right = TreeNode(item_set)
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 =
if isinstance(node.left, TreeNode):
r = self.dumpTreeNode(node.left, level + 1)# 递归导出子树
for k in r:
if k not in result:
result = list()
result.extend(r)
else:
if level + 1 not in result:
result = list()
result.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 = list()
result.extend(r)
else:
if level + 1 not in result:
result = list()
result.append(node.right)
return result
def main():# 测试函数主函数
test = [
'[]',
'[]',
'[,]',
'[,,,,]',
'[,,,,,,,,,,,,,]',
'[,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,]'
]
for i in range(len(test)):
s = Solution()
r = s.generateTrees(i)
s = test
r_ = json.loads(s)
print(len(r), len(r_))
for j, v in enumerate(r):
if v != r_:
print(i, v == r_, v, r_)
if __name__ == '__main__':
main()
python的类有点复杂，我是能避开就避开了 qcztsn 发表于 2018-11-16 19:51
楼主这个是leetcode上的题目吗？
是的,最近下班了就会研究这个,把自己写的代码发这里来
这个是提交通过的
上面的代码不但有正确性的限制,还有性能上面的限制
有兴趣也可以一起啊 wangqiustc 发表于 2018-11-16 18:28
python的类有点复杂，我是能避开就避开了
python3已经改进很多了,加入了保护成员和方法(名称前面加下划线)
python的类其实还是很容易的
属性和方法和其他相比更简单
二叉树搜索有什么简单的例子么，看上去好复杂，先收藏一下，之后再研究一下{:1_893:}
页:
[1]