LeetCode: 95. Unique Binary Search Trees II

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

95. Unique Binary Search Trees II

LeetCode - 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
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 参考 https://leetcode.cn/problems/unique-binary-search-trees-ii/solutions/339143/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/[95. 不同的二叉搜索树 II - 官方题解^]
 */
public List<TreeNode> generateTrees(int n) {
  if (n == 0) {
    return Collections.emptyList();
  }
  return generateTrees(1, n);
}

private List<TreeNode> generateTrees(int start, int end) {
  List<TreeNode> result = new ArrayList<>();
  if (start > end) {
    result.add(null);
    return result;
  }

  // 枚举可行根节点
  for (int i = start; i <= end; i++) {
    // 获得所有可行的左子树集合
    List<TreeNode> leftTrees = generateTrees(start, i - 1);
    // 获得所有可行的右子树集合
    List<TreeNode> rightTrees = generateTrees(i + 1, end);
    for (TreeNode left : leftTrees) {
      for (TreeNode right : rightTrees) {
        // 从左子树集合中选出一棵左子树，
        // 从右子树集合中选出一棵右子树，拼接到根节点上
        TreeNode curr = new TreeNode(i);
        curr.left = left;
        curr.right = right;
        result.add(curr);
      }
    }
  }
  return result;
}

这道题用到了回溯思想！昨天突击，又重新看了一遍回溯。有个模糊影响，但是还是要加强练习。