2018-07-29 17:42:29
問題描述:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yM3UjNyU2NiJGO0gTOiNWMklTN1kjY3czNkVDOkJGNw8CX0EzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLzM3Lc9CX6MHc0RHaiojIsJye.png)
問題求解:
本題是要求尋找一棵樹中的重複子樹,問題的難點在于如何在周遊的時候對之前周遊過的子樹進行描述和儲存。
這裡就需要使用之前使用過的二叉樹序列化的手法,将周遊到的二叉樹進行序列化表達,我們知道序列化的二叉樹可以唯一的表示一棵二叉樹,并可以用來反序列化。
想到這裡其實問題就已經解決了一大半了, 我們隻需要在周遊的過程中将每次的序列化結果儲存到一個HashMap中,并對其進行計數,如果重複出現了,那麼将目前的節點添加到res中即可。
算法改進:
上述的算法基本可以在O(n)的時間複雜度解決問題,但是其中的字元串拼接是非常耗時的,這裡可以對這個部分做出一點改進。如果我們不用序列化結果來表征一個子樹,用一個id值來表征的話,那麼就可以規避掉字元串拼接的問題。
這裡直接使用id的size來進行id的配置設定,值得注意的是由于已經給null配置設定了0,那麼每次配置設定的大小應該是size + 1。