python实现leetcode之95. 不同的二叉搜索树 II

解题思路

随机选一个元素，左子树的所有节点肯定来自左边，右子树的所有节点肯定来右边
对各子树的每一种情况，进行组合即可

95. 不同的二叉搜索树 II

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if not n: return []
        nodes = list(range(1, n+1))
        return gt(nodes)


def gt(nodes):
    if not nodes: return [None]
    trees = []
    for idx, item in enumerate(nodes):
        for left in gt(nodes[:idx]):
            for right in gt(nodes[idx+1:]):
                trees.append(TreeNode(item, left, right))
    return trees