解法一：递归

选定一个数作为根结点后，就可以确定左右子树含有结点的数值范围，然后递归地建立子树，左右子树任意组合加上根结点就可以组成一颗完整的树。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  * int val;
  5.  * TreeNode left;
  6.  * TreeNode right;
  7.  * TreeNode() {}
  8.  * TreeNode(int val) { this.val = val; }
  9.  * TreeNode(int val, TreeNode left, TreeNode right) {
  10.  * this.val = val;
  11.  * this.left = left;
  12.  * this.right = right;
  13.  * }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<TreeNode> generateTrees(int n) {
  18.         if (n == 0) {
  19.             return new LinkedList();
  20.         }
  21.         return recursion(1, n);
  22.     }
  24.     private List<TreeNode> recursion(int begin, int end) {
  25.         List<TreeNode> rootList = new LinkedList<>();
  26.         if (begin > end) {
  27.             // 防止循环不进行
  28.             rootList.add(null);
  29.             return rootList;
  30.         }
  31.         for (int i = begin; i <= end; ++i) {
  32.             List<TreeNode> leftList = recursion(begin, i - 1);
  33.             List<TreeNode> rightList = recursion(i + 1, end);
  34.             for (TreeNode leftNode : leftList) {
  35.                 for (TreeNode rightNode : rightList) {
  36.                     TreeNode temp = new TreeNode(i, leftNode, rightNode);
  37.                     rootList.add(temp);
  38.                 }
  39.             }
  40.         }
  41.         return rootList;
  42.     }
  43. }