LeetCode之Unique Binary Search Trees I and II python解法

水深无声 2021-11-24 02:06 189阅读 0赞

题：

#### Unique Binary Search Trees I ####

Given *n*, how many structurally unique **BST’s** (binary search trees) that store values 1 … *n*?

**Example:**

Input: 3
    Output: 5
    Explanation:
    Given n = 3, there are a total of 5 unique BST's:
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

题意：数字1-n可以组成多少个不同的二叉搜索树

思路：

开始想尝试用类似数字全排列的回溯方法去做，但并不是每一种全排列的方式都可以组成BST，如：以2为根节点，就只有一种BST，但全排有两种，遂不可行。

用动态规划的方法，分别计算左子树和右子树的可行个数，再相乘就是所有可能的个数。从最小的子问题依次计算，注意dp\[0\]=1，因为空子树也可以算一种BST

在下面的代码中，第一个循环对应共有几个数，第二个循环对应以哪个数为根节点。

class Solution:
        def numTrees(self, n: int) -> int:
            dp = [0 for _ in range(n+1)]
            dp[0] = 1
            for i in range(1, n+1):
                for j in range(i):
                    dp[i] += dp[j] * dp[i-1-j]
            return dp[-1]

#### Unique Binary Search Trees II ####

题：

Given an integer *n*, generate all structurally unique **BST’s** (binary search trees) that store values 1 … *n*.

**Example:**

Input: 3
    Output:
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
    Explanation:
    The above output corresponds to the 5 unique BST's shown below:
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

题意：这次要把所有的二叉搜索树都打印出来

思路：

这个问题的解决思路依然是从小到大，在循环中调用递归函数求解子问题，并记录下来。具体是每次选取一个结点为根，然后递归求解左右子树的所有结果，然后每一个左子树的结果和每一个右子树的结果匹配生成一种最终结果，总共有左右子树数量的乘积种情况，  
上下两道题的解题依据都是：当数组为 1，2，3，4，… i，… n时，基于以下原则的BST建树具有唯一性：  
以i为根节点的树，其左子树一定由\[1, i-1\]构成（注意是构成，该左子树并不唯一）， 其右子树一定由\[i+1, n\]构成。

**下面代码中，每一个res列表中存储的都是\[start, end\]数据内，以 i 为根节点的所有树。**

# 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]:
            if not n:return []
            res = self.helper(1, n)
            return res
        def helper(self, start, end):
            res = []
            if start > end:
                res.append(None)
                return res
            for i in range(start, end+1):
                left = self.helper(start, i-1)
                right = self.helper(i+1, end)
                for item1 in left:
                    for item2 in right:
                        item = TreeNode(i)
                        item.left = item1
                        item.right = item2
                        res.append(item)
            return res