156 - 95 不同的二叉搜索树2

题目

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树：

1 3 3 2 1 / / / 3 2 1 1 3 2 / / 2 1 2 3

解答

不同的二叉树1是计算有多少个，现在是要把全部情况列出来。

递归

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def helper(start, end):
            if start > end:
                return [None, ]
            all_trees = []
            for i in range(start, end+1):
                left_trees = helper(start, i-1)
                right_trees = helper(i+1, end)
                for l in left_trees:
                    for r in right_trees:
                        current_tree = TreeNode(i)
                        current_tree.left = l
                        current_tree.right = r
                        all_trees.append(current_tree)
            return all_trees
        return helper(1, n) if n else []

Runtime: 52 ms, faster than 87.17% of Python3 online submissions for Unique Binary Search Trees II.

Memory Usage: 14.2 MB, less than 80.00% of Python3 online submissions for Unique Binary Search Trees II.

看不懂的解

https://leetcode.com/problems/unique-binary-search-trees-ii/discuss/31495/Should-be-6-Liner

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def node(val, left, right):
            node = TreeNode(val)
            node.left = left
            node.right = right
            return node

        def trees(first, last):
            return [node(root, left, right)
                    for root in range(first, last+1)
                    for left in trees(first, root-1)
                    for right in trees(root+1, last)]or[None]
        return trees(1, n) if n != 0 else []

Runtime: 60 ms, faster than 56.45% of Python3 online submissions for Unique Binary Search Trees II.

Memory Usage: 14.8 MB, less than 73.33% of Python3 online submissions for Unique Binary Search Trees II.

动态规划

https://leetcode.com/problems/unique-binary-search-trees-ii/discuss/31523/DP-solution-in-Python

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0:
            return []
        tree_list = [[[None]] * (n+2) for i in range(n+2)]
        for i in range(1, n+1):
            tree_list[i][i] = [TreeNode(i)]
            for j in range(i-1, 0, -1):
                tree_list[j][i] = []
                for k in range(j, i+1):
                    for left in tree_list[j][k-1]:
                        for right in tree_list[k+1][i]:
                            root = TreeNode(k)
                            root.left, root.right = left, right
                            tree_list[j][i].append(root)
        return tree_list[1][n]

Runtime: 44 ms, faster than 98.40% of Python3 online submissions for Unique Binary Search Trees II.

Memory Usage: 13.4 MB, less than 100.00% of Python3 online submissions for Unique Binary Search Trees II.