填空题

合成二叉树

Question

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

如有两棵二叉树:

T1:        T2:
   1          1
  / \        / 
 1   1      1

他们合并后为:

T3:
    1
   / \
  1   1
 /   / \
1   1   1