LeetCode95UniqueBinarySearchTreeII(Python详解及实现)

【题目】

Given an integer n, generate allstructurally unique BST's (binary search trees) that store values 1...n.

For example,

Given n = 3, your program should return all5 unique BST's shown below.

  1         3     3     2      1

   \       /     /     / \      \

    3     2     1     1   3      2

   /     /       \                 \

  2     1         2                 3

这道题与94题类似，94题求得是符合条件的二叉树的棵树，这题是返回所有符合条件的二叉查找树。

【思路】

二叉查找树，也称为二叉搜索树，二叉排序树。它可以是一棵空树，也可以是具有下列性质的二叉树：

         若二叉查找树的左子树不空，则左子树上的所有结点的值均小于它的根结点的值，若右子树不为空，则右子树上所有结点的值均大于它的根结点的值；它的左右子树也分别为二叉排序树。

         对于求数量的题目一般考虑DP，而枚举所有符合条件的情况，一般用DFS。每次选取其中一个为根结点，然后求左右子树。当输入n时，二叉查找树由【1,2，···i,···n】构成

根据二叉查找树的构成性质：当选择i为根结点时，【1,2，···i-1】构成其左子树，【i+1,i+2,···，n】构成其右子树。

当b > e 时，返回空(注意不是null)；

当b <= e时，用leftTree 和rightTree来分别接收左右子树。

【Python实现】

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
class Solution(object):
   def generateTrees(self, n):
       """
       :type n: int
       :rtype: List[TreeNode]
       """
       if n == 0:
           return []
       return self.dfs(1,n)
       
   def dfs(self, b, e):#b,e为开始和结束数字
       if b > e:
           return [None]
       res = []
       for rootVal in range(b, e + 1):
           leftTree = self.dfs(b, rootVal - 1)
           rightTree = self.dfs(rootVal + 1, e)
           for i in leftTree:
                for j in rightTree:
                    root = TreeNode(rootVal)
                    root.left = i
                    root.right = j
                    res.append(root)
       return res
 
if __name__ == '__main__':
    S= Solution()
   S.generateTrees(3)