96. Unique Binary Search Trees

题目要求

给出节点的数量，求所有合法的二叉查找树的数量

解题过程

考虑以树上任意一个节点x为根的合法二叉查找树的数量k。
假设其右子树的合法二叉树数量为r，左子树的合法二叉树数量为l，易得以x为根的合法二叉树数量为k = r * l。
考虑边界条件，当x为叶节点时k = 1。
综上可以推出