题目

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

示例:

  1. 输入: 3
  2. 输出:
  3. [
  4.   [1,null,3,2],
  5.   [3,2,null,1],
  6.   [3,1,null,null,2],
  7.   [2,1,3],
  8.   [1,null,2,null,3]
  9. ]
  10. 解释:
  11. 以上的输出对应以下 5 种不同结构的二叉搜索树：
  13.    1         3     3      2      1
  14.     \       /     /      / \      \
  15.      3     2     1      1   3      2
  16.     /     /       \                 \
  17.    2     1         2                 3

方案一

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func generateTrees(n int) []*TreeNode {
  10.     if n == 0 {
  11.         return []*TreeNode{}
  12.     }
  13.     return helper(1, n)
  14. }
  16. func helper(start, end int) []*TreeNode {
  17.     if start > end {
  18.         return []*TreeNode{nil} // 这里必须返回 nil 数组
  19.     }
  20.     all_trees := []*TreeNode{}
  21.     for i := start; i <= end; i++ { 
  22.         // 所有可能的左右子树
  23.         left_trees := helper(start, i - 1)
  24.         right_trees := helper(i + 1, end)
  25.         for _, l := range left_trees {
  26.             for _, r := range right_trees {
  27.                 all_trees = append(all_trees, &TreeNode{
  28.                     Val: i,
  29.                     Left: l,
  30.                     Right: r,
  31.                 })
  32.             }
  33.         }
  34.     }
  35.     return all_trees
  36. }

原文

https://leetcode-cn.com/explore/featured/card/recursion-i/260/conclusion/1233/
https://leetcode-cn.com/explore/featured/card/recursion-i/260/conclusion/1234/