95. Unique Binary Search Trees II

https://leetcode.com/problems/unique-binary-search-trees-ii/

题目介绍:

题目会给你一个数字 n，你要用范围 1 to n 建立所有的二元搜寻树(binary search trees)

Example1:

解法:

这题算是很基本的Divide and Conquer，所以有点不知道要打什麽

总之先上程序码吧

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        
        def BST(arr):
            
            if len(arr) == 0:
                return [None]
            
            res = []
            for i in range(len(arr)):
                leftTree = BST(arr[:i])
                rightTree = BST(arr[i+1:])
                
                for l in leftTree:
                    for r in rightTree:
                        res.append(TreeNode(arr[i],l, r))
                        
            return res
                
        return BST([i for i in range(1, n+1)])

步骤:

1. 一开始先列出要建成节点的数字*[1~n]*
2. 接着按照BST的规则: 左子树所有node的值小於根的值、右子树所有node的值大於根的值，区分要建成左子树和右子树的数字，并建立左子树leftTree和右子树rightTree
3. 组成所有可能的结构

快一点的解法:

这个方法把输入改成有开头和结尾，并用一个 memory 去记下曾经组过的树，若之後再次遇到同样的开头和结尾，就可以拿出储存值省略一些步骤了

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        
        memory = {}
        def BST(start, end):
            
            if start > end:
                return [None]
            if (start, end) in memory:
                return memory[(start, end)]
            
            res = []
            for i in range(start, end+1):
                leftTree = BST(start, i-1)
                rightTree = BST(i+1, end)
                
                for l in leftTree:
                    for r in rightTree:
                        res.append(TreeNode(i, l, r))
                        
            memory[(start, end)] = res
            return res
                
        return BST(1, n)

闲聊:

今天是第二天，题目比昨天简单一点

本来想说竟然都打这篇了，乾脆连他的类似题目Unique Binary Search Trees 也一起打

後来想想算了，过几天後LeetCode可能就把这题当作当天的题目

所以之後遇到再说吧!