652. Find Duplicate Subtrees

发表于 | 分类于 | |

652. Find Duplicate Subtrees

题目描述

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

1
2
3
4
5
6
7
8
Example 1: 
        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

The following are two duplicate subtrees:

1
2
3
  2
 /
4

and

1
4

Therefore, you need to return above trees’ root in the form of a list.

题目大意

寻找重复子树

解题思路

采用辅助字典
利用字符串模拟树形结构，以字符串为key，当字典值为2时，则表示有相等的树，返回此树即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
        var dict = [String: Int]()
        var ans = [TreeNode?]()
        func find(root: TreeNode?) -> String {
            guard let node = root else { return "." }
            let s = "\(node.val)\(find(root: node.left))\(find(root: node.right))"
            let v = (dict[s] ?? 0) + 1
            if v == 2 {
                ans.append(node)
            }
            dict[s] = v
            return s
        }
        find(root: root)
        return ans
    }
}
0%