天天看點

Leetcode 652.尋找重複的子樹

尋找重複的子樹

給定一棵二叉樹,傳回所有重複的子樹。對于同一類的重複子樹,你隻需要傳回其中任意一棵的根結點即可。

兩棵樹重複是指它們具有相同的結構以及相同的結點值。

Leetcode 652.尋找重複的子樹

下面是兩個重複的子樹:

Leetcode 652.尋找重複的子樹

是以,你需要以清單的形式傳回上述重複子樹的根結點。

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.

Leetcode 652.尋找重複的子樹

繼續閱讀