[Leetcode][python]Unique Binary Search Trees II

喜欢ヅ旅行 2022-06-11 04:11 142阅读 0赞

## 题目大意 ##

给出一个n，求1-n能够得到的所有二叉搜索树，输出所有树

## 解题思路 ##

递归拼接树

该题较难，参考[题解][Link 1]的思路。

从start到end，先把左右字数的所有可能先迭代出来，之后递归加入左右字数，生成每一颗新树。

## 代码 ##

class Solution(object):
        def generateTrees(self, n):
            if n == 0:
                return []
            return self.helper(1, n)
    
        def helper(self, start, end):
            result = []
            if start > end:
                result.append(None)
                return result
    
            for i in range(start, end + 1):
                # generate left and right sub tree
                leftTree = self.helper(start, i - 1)
                rightTree = self.helper(i + 1, end)
                # link left and right sub tree to root(i)
                for j in range(len(leftTree)):
                    for k in range(len(rightTree)):
                        root = TreeNode(i)
                        root.left = leftTree[j]
                        root.right = rightTree[k]
                        result.append(root)
    
            return result

## 总结 ##

[Link 1]: https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73055

发表评论取消回复

表情：

评论列表（有 0 条评论，142人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Binary Search Tree)501. Find Mode in Binary Search Tree

1.问题 Given the root of a binary search tree (BST) with duplicates, return all the mod

绝地灬酷狼/ 2023年09月26日 20:39/ 0 赞/ 16 阅读

相关 LeetCode - Medium - 95. Unique Binary Search Trees II

Topic Dynamic Programming Tree Description [https://leetcode.com/problems/u

比眉伴天荒/ 2022年10月06日 06:58/ 0 赞/ 56 阅读

相关 leetcode 95. Unique Binary Search Trees II | 96. Unique Binary Search Trees

95. Unique Binary Search Trees II [https://leetcode.com/problems/unique-binary-search

布满荆棘的人生/ 2022年09月10日 03:13/ 0 赞/ 171 阅读

相关 LeetCode95—Unique Binary Search Trees II

LeetCode95—Unique Binary Search Trees II 分治法求解结构不同BST（查找二叉树）原题 > Given n, genera

阳光穿透心脏的1/2处/ 2022年08月21日 01:27/ 0 赞/ 8 阅读

相关 Unique Binary Search Trees II--LeetCode

题目： Given n, generate all structurally unique BST's (binary search trees) that sto

矫情吗；*/ 2022年08月05日 14:18/ 0 赞/ 149 阅读

相关 [leetcode]95. Unique Binary Search Trees II

题目链接：[95. Unique Binary Search Trees II][] Given an integer n, generate all structurall

左手的ㄟ右手/ 2022年07月21日 02:22/ 0 赞/ 175 阅读

相关 [Leetcode][python]Unique Binary Search Trees II

题目大意给出一个n，求1-n能够得到的所有二叉搜索树，输出所有树解题思路递归拼接树该题较难，参考[题解][Link 1]的思路。从start到end

喜欢ヅ旅行/ 2022年06月11日 04:11/ 0 赞/ 143 阅读

相关 Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST

刺骨的言语ヽ痛彻心扉/ 2021年12月17日 10:35/ 0 赞/ 218 阅读

相关 Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...

刺骨的言语ヽ痛彻心扉/ 2021年12月17日 10:29/ 0 赞/ 236 阅读

相关 Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST's (binary search trees) that s

逃离我推掉我的手/ 2021年11月17日 04:10/ 0 赞/ 177 阅读