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

zerglurker

题目:

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

解题要点:1 树类型的算法,一般都可以用递归来解决,因此首先考虑递归2 接着,要考虑如何生成树3 最后考虑如何输出树具体内容看下面代码注释import json

[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()

wangqiustc

python的类有点复杂，我是能避开就避开了

zerglurker

qcztsn 发表于 2018-11-16 19:51
楼主这个是leetcode上的题目吗？

是的,最近下班了就会研究这个,把自己写的代码发这里来
这个是提交通过的
上面的代码不但有正确性的限制,还有性能上面的限制
有兴趣也可以一起啊

zerglurker

wangqiustc 发表于 2018-11-16 18:28
python的类有点复杂，我是能避开就避开了

python3已经改进很多了,加入了保护成员和方法(名称前面加下划线)
python的类其实还是很容易的
属性和方法和其他相比更简单

小黑LLB

二叉树搜索有什么简单的例子么，看上去好复杂，先收藏一下，之后再研究一下