尋找重複的子樹
給定一棵二叉樹,傳回所有重複的子樹。對于同一類的重複子樹,你隻需要傳回其中任意一棵的根結點即可。
兩棵樹重複是指它們具有相同的結構以及相同的結點值。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5CZllzYihjZkVDMyM2M2ETZiNzMkV2YlVjMwYzNxMzN38CXxEzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL3M3Lc9CX6MHc0RHaiojIsJye.png)
下面是兩個重複的子樹:
是以,你需要以清單的形式傳回上述重複子樹的根結點。
Intuition
We can serialize each subtree. For example, the tree
can be represented as the serialization 1,2,#,#,3,4,#,#,5,#,#, which is a unique representation of the tree.
Algorithm
Perform a depth-first search, where the recursive function returns the serialization of the tree. At each node, record the result in a map, and analyze the map after to determine duplicate subtrees.