Unique Binary Search Trees II

描述

Given n, generate all structurally unique BST's (binary search trees) that store values 1…n.

For example,Given n = 3, your program should return all 5 unique BST's shown below.

  1.    1         3     3      2      1
  2.     \       /     /      / \      \
  3.      3     2     1      1   3      2
  4.     /     /       \                 \
  5.    2     1         2                 3

分析

见前面一题。

代码

  1. // Unique Binary Search Trees II
  2. // 时间复杂度TODO，空间复杂度TODO
  3. public class Solution {
  4.     public List<TreeNode> generateTrees(int n) {
  5.         if (n == 0) return new ArrayList<>();
  6.         return generate(1, n);
  7.     }
  8.     private static List<TreeNode > generate(int start, int end) {
  9.         List<TreeNode> subTree = new ArrayList<>();
  10.         if (start > end) {
  11.             subTree.add(null);
  12.             return subTree;
  13.         }
  14.         for (int k = start; k <= end; k++) {
  15.             List<TreeNode> leftSubs = generate(start, k - 1);
  16.             List<TreeNode> rightSubs = generate(k + 1, end);
  17.             for (TreeNode i : leftSubs) {
  18.                 for (TreeNode j : rightSubs) {
  19.                     TreeNode node = new TreeNode(k);
  20.                     node.left = i;
  21.                     node.right = j;
  22.                     subTree.add(node);
  23.                 }
  24.             }
  25.         }
  26.         return subTree;
  27.     }
  28. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/bst/unique-binary-search-trees-ii.html