吾爱破解 - 52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 3072|回复: 5
收起左侧

[Python 转载] [笔记]算法学习:不同的二叉搜索树 II

[复制链接]
zerglurker 发表于 2018-11-16 17:10
本帖最后由 wushaominkk 于 2018-11-18 15:53 编辑

题目:

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/

解题要点:1 树类型的算法,一般都可以用递归来解决,因此首先考虑递归2 接着,要考虑如何生成树3 最后考虑如何输出树具体内容看下面代码注释import json
[Python] 纯文本查看 复制代码
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
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()

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

wangqiustc 发表于 2018-11-16 18:28
python的类有点复杂,我是能避开就避开了
 楼主| zerglurker 发表于 2018-11-16 21:35
qcztsn 发表于 2018-11-16 19:51
楼主这个是leetcode上的题目吗?

是的,最近下班了就会研究这个,把自己写的代码发这里来
这个是提交通过的
上面的代码不但有正确性的限制,还有性能上面的限制
有兴趣也可以一起啊
 楼主| zerglurker 发表于 2018-11-16 21:36
wangqiustc 发表于 2018-11-16 18:28
python的类有点复杂,我是能避开就避开了

python3已经改进很多了,加入了保护成员和方法(名称前面加下划线)
python的类其实还是很容易的
属性和方法和其他相比更简单
小黑LLB 发表于 2019-2-15 21:44
二叉树搜索有什么简单的例子么,看上去好复杂,先收藏一下,之后再研究一下
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则

返回列表

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2025-4-5 05:52

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表