Leetcode 95. 不同的二叉搜索树 II

题目描述

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

示例 1:

解法

参考Leetcode 96. 不同的二叉搜索树

计算二叉树的种类数时，只需要知道整数的个数即可，此处需要计算出二叉树的节点值，所以需要提供每个节点的整数值。

不妨以 表示从整数 到整数 构成的所有二叉树，不包含 的值，则该问题只需要计算出 即可。

的值为以整数 到整数 之间的每一个数字为根节点，左子树的情况与右子树的情况乘积的累加和。

# 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: int) -> List[TreeNode]:
        def tree(i,j):
            if j==i:
                return [None]
            if j==i+1:
                return [TreeNode(i)]
            ret=[]
            for t in range(i,j):
                left,right=tree(i,t),tree(t+1,j)
                tmp=[]
                for lnode in left:
                    for rnode in right:
                        tnode=TreeNode(t)
                        tnode.left,tnode.right=lnode,rnode
                        tmp.append(tnode)
                ret.extend(tmp)
            return ret
        return [] if n==0 else tree(1,n+1)