95 Unique Binary Search Trees II

请教一下，95题，solution如下。 那个base case为什么是start > end？如果只剩一个数，start == end是有可能的，想不明白为什么会start > end

1. class Solution {
   
2.   public LinkedList<TreeNode> generate_trees(int start, int end) {
   
3.     LinkedList<TreeNode> all_trees = new LinkedList<TreeNode>();
   
4.     if (start > end) {
   
5.       all_trees.add(null);
   
6.       return all_trees;
   
7.     }
   
8. 
   
9.     // pick up a root
   
10.     for (int i = start; i <= end; i++) {
    
11.       // all possible left subtrees if i is choosen to be a root
    
12.       LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);
    
13. 
    
14.       // all possible right subtrees if i is choosen to be a root
    
15.       LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);
    
16. 
    
17.       // connect left and right trees to the root i
    
18.       for (TreeNode l : left_trees) {
    
19.         for (TreeNode r : right_trees) {
    
20.           TreeNode current_tree = new TreeNode(i);
    
21.           current_tree.left = l;
    
22.           current_tree.right = r;
    
23.           all_trees.add(current_tree);
    
24.         }
    
25.       }
    
26.     }
    
27.     return all_trees;
    
28.   }
    
29. 
    
30.   public List<TreeNode> generateTrees(int n) {
    
31.     if (n == 0) {
    
32.       return new LinkedList<TreeNode>();
    
33.     }
    
34.     return generate_trees(1, n);
    
35.   }
    
36. }

复制代码

start == end是有可能啊，不过这个时候是单个节点。这里写的是start > end, 也就是说直接成为null了，作为base case更有优势啊

为什么成为null的时候，是start > end而不是start==end？

小水 发表于 2020-2-20 05:17
为什么成为null的时候，是start > end而不是start==end？

就像你说的啊，start和end相等的时候还有一个数啊，这个数可以构成一个节点。