原题地址（中等）

方法1—分治递归

该方法参考自力扣官方题解

思路


二叉搜索树定义**：

  • 或者是一棵空树；
  • 或者是一棵具有以下性质的二叉树：
    • 若左子树不空，则根节点大于左子树所有节点；
    • 若右子树不空，则根节点大于右子树所有节点；
    • 它的左右子树也分别为二叉搜索树。

我们可以发现，二叉搜索树天然具有递归性质，并且子树与原树具有完全相同的性质，这符合分治的特征，所以用递归分治来做非常合适。

分治特征：原问题可以划分为结构完全相同的子问题，子问题间相互独立，可以通过求解子问题来得到原问题的解。

我们定义函数 generateTrees(begin, end) 来生成以 begin, begin+1, ......, end 为根的所有二叉搜索树，并返回列表 [root1, root2, root3, root4] ，列表中存的是每棵树的根节点。

函数 generateTrees(begin, end) 实现过程：

  1. 递归终止条件：如果 begin>end ，返回一个含有 None 的列表；
  2. 遍历 [begin, end+1] ，以各点为根：
    • 求出所有可能的左子树；
    • 求出所有可能的右子树；
    • 二重循环遍历左右子树，得到完整的二叉树；
  3. 返回所有的二叉树。

python代码

  1. class Solution:
  2.     def generateTrees(self, n: int) -> List[TreeNode]:
  3.         def generateTrees(begin, end):
  4.             if begin > end:
  5.                 return [None]
  7.             ans = []
  8.             for i in range(begin, end+1):
  9.                 left = generateTrees(begin, i-1)
  10.                 right = generateTrees(i+1, end)
  11.                 for l in left:
  12.                     for r in right:
  13.                         root = TreeNode(i)
  14.                         root.left = l
  15.                         root.right = r
  16.                         ans.append(root)
  17.             return ans
  19.         return generateTrees(1, n) if n else []