合成二叉树_牛客题霸

牛牛有棵二叉树，其编号为。牛牛会将这棵树合并为一棵。牛牛每次可以从这棵树中挑选出两棵树，并创建一个新根且节点权值为，该新根的左儿子为这两棵树中节点数量较少的根节点，右儿子为节点数量较多的根节点。每次合并的花费为两棵树的大小之和，得到的新树的编号为当前最大编号加一。若的大小不是唯一的，那么牛牛会换成和大小相同且编号最小的树参与合并，同理。当和大小相等时，牛牛会将编号较小的树作为左儿子，编号较大的树作为右儿子。牛牛想在花费最小的情况下将这棵树合并为一棵，请你返回最后的树。如有两棵二叉树: T1: T2: 1 1 \ 1 1 1 他们合并后为: T3: 1 \ 1 1 \ 1 1 1

示例1

输入

[{1,1,1},{1,1}]

输出

{1,1,1,1,#,1,1}

说明

如题意中所描述。

示例2

输入

[{1},{1,1},{1},{1,#,1,1}]

输出

{1,1,1,1,1,1,1,#,#,#,#,1,#,#,1,#,#,1}

说明

第一次牛牛会取编号为的树和编号为的树合并为大小为的树，其花费为，编号为。
第二次牛牛会取编号为的树和编号为的树合并为大小为的树，其花费为，编号为。
第三次牛牛会取编号为的树和编号为的树合并为大小为的树，其花费为。

备注:

，每棵树的节点个数，棵树总节点个数。