95-不同的二叉搜索树-ii

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

---

示例

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

---

解法

核心思想：利用二叉搜索树的性质，左子树只能比当前结点小，右子树只能比当前结点大。每个结点均有可能做为根结点。

技巧点：利用lru_cache收集每一个返回的值

import functools
class Solution:
    # Notice：返回值应为List[TreeNode]
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0: return []
        # 收集每次的返回值，组成缓存列表,None为动态调节大小
        @functools.lru_cache(None)
        def helper(start, end):
            res = []
            if start > end:
                res.append(None)
            for val in range(start, end + 1):
                # 左子树均小于val
                for left in helper(start, val - 1):
                    # 右子树均大于val
                    for right in helper(val + 1, end):
                        # 构建树节点
                        root = TreeNode(val,left,right)
                        res.append(root)
            return res
        return helper(1, n)

---

相关信息

LeetCode：Discussion | Solution