96. Unique Binary Search Trees (Tree; DFS)

class Solution {
public:
    int numTrees(int n) {
        return dfs(1,n);
    }
   
    int dfs(int start, int end)
    {
        int leftNum = 0;
        int rightNum = 0;
        int num = 0;
 
        for ( int i = start; i <= end; i++) //枚举左、右子数节点分配的所有情况
        {
            if(i!=start) leftNum = dfs(start,i-1); //左子树
            else leftNum = 1;
            if(i!=end) rightNum = dfs(i+1,end); //右子树
            else rightNum = 1;
            num += leftNum*rightNum;
        }
       
        return num;
    }
};