[Swift]LeetCode652. 寻找重复的子树 | 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 structu

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.

Example 1:

        1       /       2   3     /   /     4   2   4       /      4

The following are two duplicate subtrees:

      2     /    4

and

    4

Therefore,you need to return above trees‘ root in the form of a List.

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

        1       /       2   3     /   /     4   2   4       /      4

下面是两个重复的子树：

      2     /    4

和

    4

因此，你需要以列表的形式返回上述重复子树的根结点。

Runtime: 72 ms Memory Usage: 26.2 MB

 1 /** 2  * DeFinition for a binary tree node. 3  * public class TreeNode { 4  *     public var val: Int 5  *     public var left: TreeNode? 6  *     public var right: TreeNode? 7  *     public init(_ val: Int) { 8  *         self.val = val 9  *         self.left = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {16         var res:[TreeNode?] = [TreeNode?]()17         var m:[String:Int] = [String:Int]()18         helper(root,&m,&res)19         return res20     }21     22     func helper(_ node: TreeNode?,_ m:inout [String:Int],_ res:inout [TreeNode?]) -> String23     {24         if node == nil {return "#"}25         var str:String = String(node!.val) + "," + helper(node!.left,&res) + "," + helper(node!.right,&res)26         if m[str] == 127         {28             res.append(node)29         }30         m[str,default:0] += 131         return str32     }33 }

72ms

 1 /** 2  * DeFinition for a binary tree node. 3  * public class TreeNode { 4  *     public var val: Int 5  *     public var left: TreeNode? 6  *     public var right: TreeNode? 7  *     public init(_ val: Int) { 8  *         self.val = val 9  *         self.left = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {16         var map = [String: Int]()17         var result = [TreeNode?]()18         var inorderT = findDuplicateSubtrees(root,&map,&result)19         20         return result21     }22     23     func findDuplicateSubtrees(_ root: TreeNode?,_ map: inout [String: Int],_ result: inout [TreeNode?]) -> String {24         guard let root = root else { 25             return ""26         }27         28         var str = "("29         str += findDuplicateSubtrees(root.left,&result)30         str += "\(root.val)"31         str += findDuplicateSubtrees(root.right,&result)32         str += ")"33         34         map[str] = (map[str] ?? 0) + 135         36         if map[str] == 2 {37             result.append(root)38         }39         40         return str                                41     }42 }

72ms

 1 /** 2  * DeFinition for a binary tree node. 3  * public class TreeNode { 4  *     public var val: Int 5  *     public var left: TreeNode? 6  *     public var right: TreeNode? 7  *     public init(_ val: Int) { 8  *         self.val = val 9  *         self.left = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {16         var res:[TreeNode?] = [TreeNode?]()17         var m:[String:Int] = [String:Int]()18         helper(root,default:0] += 131         return str32     }33 }

88ms

 1 class Solution { 2     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] { 3         var result = [TreeNode]() 4         var dict = [String: Int]() 5         helper(&result,&dict,root) 6         return result 7     } 8      9     func helper(_ result: inout [TreeNode],_ dict: inout [String: Int],_ root: TreeNode?) -> String {10         guard let root = root else { return "#" }11         12         let left = helper(&result,root.left)13         let right = helper(&result,root.right)14         15         let s = "\(root.val)" + "," + left + "," + right        16         if let count = dict[s] {17             if count == 1 {18                 result.append(root)19             }20             dict[s] = count + 121         } else {22             dict[s] = 123         }24         25         return s26     }27 }

92ms

 1 class Solution { 2     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] { 3         var subTree: [String: Int] = [:] 4         var res: [TreeNode?] = [] 5         helper(root,&subTree,&res) 6         return res 7     } 8      9     private func helper(_ root: TreeNode?,_ subTree: inout [String: Int],_ res: inout [TreeNode?]) -> String {10         guard let root = root else { return "#" }11         let serializedString = "\(String(root.val)) \(helper(root.left,&res)) \(helper(root.right,&res))"12         13         if let count = subTree[serializedString] {14             if count == 1 {15                 res.append(root)16             }17             subTree[serializedString] = count + 118         } else {19             subTree[serializedString] = 120         }21         22         return serializedString23     }24 }

96ms

 1 class Solution { 2     var foundSubtrees = Set<String>() 3     var solution = [String: TreeNode]() 4      5     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] { 6         guard let root = root else { return [] } 7         solve(root) 8         return [TreeNode](solution.values) 9     }10     11     func solve(_ node: TreeNode) -> String {12         let leftKey = node.left.map { return solve($0) } ?? "NL"13         let rightKey = node.right.map { return solve($0) } ?? "NR"14         let key = "[\(String(node.val))/\(leftKey):\(rightKey)]"15         if foundSubtrees.contains(key) {16             solution[key] = node17         } else {18             foundSubtrees.insert(key)19         }20         return key21     }22 }23 24 extension TreeNode: Hashable {25     public var hashValue: Int {26         return val27     }28     29     static public func == (lhs: TreeNode,rhs: TreeNode) -> Bool {30         return lhs.val == rhs.val31     }32 }

100ms

 1 class Solution { 2     var res: [TreeNode?] = [] 3     var map: [String: Int] = [:] 4     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] { 5         preorder(root) 6         return res 7     } 8      9     private func preorder(_ root: TreeNode?) -> String {10         11         guard let root = root else { return "#"}12         let serial = "\(root.val),\(preorder(root.left)),\(preorder(root.right))"13         if map[serial] == 1 { res.append(root) }14         15         map[serial,default: 0] += 116         return serial17     }18 }

104ms

 1 class Solution { 2     var ans = [TreeNode]() 3     var subTrees = [String : Int]() 4      5     func collect(node_: TreeNode?) -> String { 6         guard let node = node_ else { return "#" } 7          8         let serial = "\(node.val),\(collect(node_: node.left)),\(collect(node_: node.right))" 9         10         if let count = subTrees[serial] {11             subTrees[serial] = count + 112             if count + 1 == 2 {13                 ans.append(node)14             }15         } else {16             subTrees[serial] = 117         }18         return serial19         20     }21     22     23     func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {24         collect(node_: root)25         return ans26     }27 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode652. 寻找重复的子树 | Find Duplicate Subtrees全部内容，希望文章能够帮你解决[Swift]LeetCode652. 寻找重复的子树 | Find Duplicate Subtrees所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。