对于一棵 nnn 个节点的二叉树,记其前序遍历为 PPP,中序遍历为 QQQ,后序遍历为 RRR。
对于一个长度为 mmm 的全排列 AAA,记 f(A)f(A)f(A) 为 AAA 在所有 mmm 的全排列中的字典序排名是第几小的,或者说是康托展开的结果。
那么,记 g(n)g(n)g(n) 为 f(P)+f(Q)+f(R)f(P)+f(Q)+f(R)f(P)+f(Q)+f(R) 的最大值,在 nnn 较大的时候,能否求出 g(n)g(n)g(n),构造使得 f(P)+f(Q)+f(R)f(P)+f(Q)+f(R)f(P)+f(Q)+f(R) 最大的二叉树?如果不能,能否构造较优的二叉树使得 f(P)+f(Q)+f(R)f(P)+f(Q)+f(R)f(P)+f(Q)+f(R) 尽可能大?