警示后人
查看原帖
警示后人
537046
大眼仔Happy楼主2024/10/23 08:19

关于此题哈希做法。

对于题解中的哈希中序遍历,其实不只是中序遍历对应点的值。对于权值相同的一棵树,单纯只哈希值会使得这个哈希值丧失掉树的形态的信息。

解决方法有两种:

  • 第一种是左右子树带权,就是题解的做法。

  • 第二种就是同时哈希上中序遍历对应点的深度。

事实上个人认为第二种更优秀一点。

第一种做法存在的隐患已经有帖子展示过了,要一直调参,可能还要调的比较大,然后大概率爆 long long 了吧,不然写三模哈希都过不了。

第二种做法冲突更小,也比较好写,试了一下自然溢出就可以了。

2024/10/23 08:19
加载中...