参考答案

递归, 函数返回从 l 到 r 区间, 所有构造的可能情况. 到达每一个点的时候, 左子树可以有 0,1,2,..,r-l-1 个节点, 右子树可以有 r-l-1,r-l-2,r-l-3,...,2,1,0 个节点, 对于左右子树的每一种节点数量递归处理,得到左右子树在当前数量可能的所有情况, 分别进行组合, 将组合后所有情况返回作为当前子树的所有情况. 假如左右子树各为 3 个节点 5 种情况, 则当前节点作为根节点时共 25 种情况.