95.Unique Binary Search Trees II

95.Unique Binary Search Trees II

這一題給n，把n所有的樹列出來 n=3, 要把如下五顆樹全部找到

這題要用回朔法，重點思考是
以i來假設尋訪的樹根
左邊小於樹根 (1, i-1…..)
右邊大於樹根 (i+1…., n)
一直列舉，直到左子樹大於右子樹的時候停下來

然後在進行回朔時，每次回朔都要把該起點的樹全部存起來
以上圖的1為例子的話
左邊就是 null
右邊有兩顆樹，2->3，3->2
然後互相去交錯就可以得到根為1全部的樹

核心思考是從樹的最深層葉子從後想到根部

List<TreeNode> generate95(int start, int end){
  List<TreeNode> trees = new ArrayList<>();
  if(start > end){ 
      trees.add(null);
      return trees;
  }
  for (int i = start; i <= end; i++) { //start 從一開始  所以end是 <=
      List<TreeNode> left = generate95(start, i-1); //壓縮樹的空間直到結束
      List<TreeNode> right = generate95(i+1, end);  //壓縮樹的空間直到結束
      for (TreeNode l : left) {  //左右子樹的交互
          for (TreeNode r : right) {
              TreeNode node = new TreeNode(i);
              node.left = l;
              node.right = r;
              trees.add(node);
          }
      }

  }
  return trees;
}
public List<TreeNode> generateTrees(int n) {
  return generate95(1, n);
}