首页 > 代码库 > LeetCode "Unique Binary Search Trees"

LeetCode "Unique Binary Search Trees"

Another recursion-style problem.

1. Each count of sub-solution with a certain root should contribute to final count

2. With a certain root, the num of left child sub-tree multiply the right one, is the current count

1A, YEAH!

class Solution {public:    int numTrees(int n) {        if (n <= 1) return 1;        if (n == 2) return 2;        int cnt = 0;        for (int i = 1; i <= n; i++)        {            int r1 = numTrees(i - 1);            int r2 = numTrees(n - i);            cnt += r1 * r2;        }        return cnt;    }};