Unique Binary Search Trees II

    容易看出，以上求解的思路非常适合用递归来处理，接下来便是设计递归的终止步、输入参数和返回结果了。由以上分析可以看出递归严重依赖数的区间和i，那要不要将i也作为输入参数的一部分呢？首先可以肯定的是必须使用『数的区间』这两个输入参数，又因为是随着『数的区间』这两个参数的，故不应该将其加入到输入参数中。分析方便，不妨设『数的区间』两个输入参数分别为start和end.

    大致的框架如上所示，我们来个简单的数据验证下，以[1, 2, 3]为例，调用堆栈图如下所示：

    1. helper(1,3)
      • [leftTree]: helper(1, 0) ==> return NULL
      • —-loop i = 2—-
      • [rightTree]: helper(2, 3)
        1. [leftTree]: helper(2,1) ==> return NULL
        2. [rightTree]: helper(3,3) ==> return node(3)
        3. [for loop]: ==> return (2->3)
      • —-loop i = 3—-
        1. [leftTree]: helper(2,2) ==> return node(2)
        2. [for loop]: ==> return (3->2)
    2. …
    1. 异常处理，返回None/NULL/null.
    2. 遍历start->end, 递归得到左子树和右子树。
    3. 两重for循环将左右子树的所有可能组合添加至最终返回结果。

    注意 DFS 辅助方法中左右子树及返回根节点的顺序。