题意：
给一个数n，返回所有能存储1到n的二叉查找树。
分析：
这是个好题，应该考虑深度优先搜索或者动态规划。
递归好理解：
遍历1到n每个数做结点。
对于每一个根节点，将左边的结点能构造出的的所有树 以及 将右边的结点能构造出的所有树 求其笛卡尔积：即双重循环遍历。
那么，怎么得到呢？递归，传的参数应该就是一串数，递归中又遍历这串数.......
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<TreeNode> generateTrees(int n) { if(n == 0) return new ArrayList<>(); return trees(1, n); } private List<TreeNode> trees(int start, int end){ List<TreeNode> roots = new ArrayList<>(); if(start > end){ roots.add(null); return roots; } for(int rootval=start; rootval<=end; rootval++){ //遍历n个数，每个都可能做根结点 List<TreeNode> lefttrees = trees(start, rootval-1); List<TreeNode> righttrees = trees(rootval+1, end); //左子树右子树的情况由于不是动态规划，没有存储，所以需要递归生成 for(TreeNode lefttree : lefttrees){ for(TreeNode righttree : righttrees){ TreeNode root = new TreeNode(rootval); root.left = lefttree; root.right = righttree; roots.add(root); } } } return roots; } }算法的思想是一样的，注意要右边的结点加值即可（注意需要重新构造）
1 2 3 4 5 6 7
对于3作为根节点左子树的形状先忽略，但肯定是12来组成
对于3作为根节点右子树的形状先忽略，但肯定是4567来构成
所以我们的dp数组里面存储的应该是List<TreeNode> 因为每N个结点有多种不同的构造形状。
所以：
3的左子树就是 dp[ 2 ]的所有
3的右子树就是dp[ 4 ]的所有，但是注意，dp[ 3 ]里存储的是 1 2 3 4而不是 4 5 6 7,所以不能直接赋值，需要构造。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public static List<TreeNode> generateTrees(int n) { List<TreeNode>[] dp = new List[n + 1]; dp[0] = new ArrayList<TreeNode>(); if (n == 0) { return dp[0]; } dp[0].add(null); for (int i = 1; i <= n; i++) { dp[i] = new ArrayList<TreeNode>(); //n个数是的所有情况 for (int rootval = 1; rootval <= i; rootval++) { //每个数都可能做根结点 int leftnum = rootval - 1; int rightnum = i - rootval; for (TreeNode left : dp[leftnum]) { for (TreeNode right : dp[rightnum]) { TreeNode root = new TreeNode(rootval); root.left = left; root.right = addVal(right, leftnum + 1); dp[i].add(root); } } } } return dp[n]; } private static TreeNode addVal(TreeNode root, int val) { if (root == null) { return null; } TreeNode node = new TreeNode(root.val + val); //对每个结点的操作应该是重新构造，否则会改变本身存储的内容 node.left = addVal(root.left, val); node.right = addVal(root.right, val); return node; } }