这道题实际上就是要获得每个结点的子结点数目。当获得子结点数目k之后,每个父结点带来C(m,k)种可能的子结点排序,最终将每个结点的子结点排序可能数相乘即可。
为求得每个结点的子结点数目,类似19年第一题,在s2后序遍历中找到对应s1先序遍历字符的位置,就得到一个数组。
如第四个用例,得到的数组应该为{11, 4, 3, 1, 2, 9, 5, 6, 7, 8, 10}。要找每个结点的字结点数,首先必须向右遍历,因为只有在其右边才可能为子结点,但在右边的还可能是兄弟结点,如何区别呢?如果为兄弟结点,则它在后序遍历中也依然在该结点的右边,若为子结点,则应该在该结点左边。
因...