leetcode-95-Unique Binary Search Trees II

Tony_Zby 发布于2019-07-31 11:11 / 1463人阅读

摘要：题目解读穷举列出所有二叉树的结构类型。重点动态规划，关注临近，，之间的关系应用穷举组合，动态规划穷举组合，适用于相邻元素有规律。处注意边界值的情况。不能有重复，遗漏。

题目解读： 穷举列出所有二叉树的结构类型。
重点： 动态规划，关注临近root，left，right之间的关系
应用：穷举组合，动态规划穷举组合，适用于相邻元素有规律。
bug处：注意边界值的情况。不能有重复，遗漏。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def generateTrees(self, n):
        def dfs(left,right):
            nodes=list()
            for root in range(left,right+1):
                print("root=>",root)
                # node=TreeNode(root)
                for node_left in dfs(left,root-1):
                    # node_left=TreeNode(val_left)
                    for node_right in dfs(root+1,right):
                        node_root=TreeNode(root)
                        node_root.left=node_left
                        # node_right=TreeNode(val_right)
                        node_root.right=node_right
                        # nodes.append(node_root)
                        nodes.append(node_root)
            return nodes or [None,]
        if n<1:
            return []
        return dfs(1,n)

if __name__=="__main__":
    n=0
    st=Solution()
    out=st.generateTrees(n)
    # out_vals=[(elem.left.val if hasattr(elem.left,"val") else None,elem.right.val if hasattr(elem.right,"val") else None) for elem in out]
    print(out)
    print(len(out))

云服务器 GPU云服务器 binary-search binary-search-tree Trees Binary

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44761.html

leetcode95-96 Unique Binary Search Trees I-II

摘要：在这里我们使用数组中下标为的位置来记录个元素可以组成的平衡二叉树的数量。在递归的过程中，我们找到以当前节点作为根节点的所有平衡二叉树，并将结果以形式返回上一级调用。题目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...

morgan 2019-08-15 11:06 评论0 收藏0
[Leetcode] Unique Binary Search Trees 唯一二叉搜索树

摘要：而根可以选择从到的任意的数，唯一二叉树的总数，就是根为到的树相加。所以该问题化简为以为根，其唯一左子树和右子树各有多少，这就是个动态规划的问题了。 Unique Binary Search Trees I && II 解法请见：https://yanjia.li/zh/2019/02/... Given n, how many structurally unique BSTs (b...

enrecul101 2019-08-14 12:38 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[LeetCode] 96. Unique Binary Search Trees I &

Unique Binary Search Trees Problem Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? Example Given n = 3, there are a total of 5 unique BSTs. 1 3 3...

nidaye 2019-08-14 15:22 评论0 收藏0
272. Closest Binary Search Tree Value II

摘要：题目链接的值大小顺序实际上就是满足的条件，所以直接中序遍历，过程中维护一个，放入个当前离最近的值，的时，新的值和的距离如果小于队首的那个值和的距离那么移除队首，如果，且新的距离大于等于队首的距离，直接退出，返回队列中的所有结果。 272. Closest Binary Search Tree Value II 题目链接：https://leetcode.com/problems... ...

NusterCache 2019-08-14 17:35 评论0 收藏0