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