LeetCode每日一题： 不同的二叉搜索树 II

看到树这个数据结构，第一个想到的方法就是我们的老朋友——递归 了
思路，使用for循环遍历1到n，i为根节点值，i的左边为左子树，i的右边为右子树，然后进行递归回溯，把所有的可能的结果都加到trees里面，最后返回。

• 代码：

class Solution {

public List<TreeNode> generateTrees(int n) {
       Solution s = new Solution();
       List<TreeNode> res = new ArrayList<TreeNode>();
       if(n == 0){
           return res;
       }
       return s.result(1,n);
    
}

public List<TreeNode> result(int left,int right){
   List<TreeNode> trees = new ArrayList<>();
    if(left > right){
            trees.add(null);
            return trees;
        }
        if(left == right){
            trees.add(new TreeNode(left));
            return trees;
        }
    for(int i = left;i <= right;i++){                   
       List<TreeNode> leftTrees = result(left,i-1);               
       List<TreeNode> rightTrees = result(i+1,right);                   
       for(TreeNode l : leftTrees){
          for(TreeNode r : rightTrees){
              TreeNode tree = new TreeNode(i);
              tree.left = l;
              tree.right = r;
              trees.add(tree);
         }
     }
    
    }         
     return trees;
}
}