[Swift]LeetCode508. 出现次数最多的子树元素和 | Most Frequent Subtree Sum

概述Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (includi

Given the root of a tree,you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tIE,return all the values with the highest frequency in any order.

Examples 1
input:

  5 /  2   -3

return [2,-3,4],since all the values happen only once,return all of them in any order. 

Examples 2
input:

  5 /  2   -5

return [2],since 2 happens twice,however -5 only occur once. 

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

给出二叉树的根，找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的元素（不限顺序）。 

示例 1
输入:

  5 /  2   -3

返回 [2,4]，所有的值均只出现一次，以任意顺序返回所有值。

示例 2
输入:

  5 /  2   -5

返回 [2]，只有 2 出现两次，-5 只出现 1 次。 

提示： 假设任意子树元素和均可以用 32 位有符号整数表示。

Runtime: 64 ms Memory Usage: 21.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 findFrequentTreeSum(_ root: TreeNode?) -> [Int] {16         var res:[Int] = [Int]()17         var m:[Int:Int] = [Int:Int]()18         var cnt:Int = 019         postorder(root,&m,&cnt)20         for (key,val) in m21         {22             if val == cnt 23             {24                 res.append(key)25             }26         }27         return res28     }29     30     func postorder(_ node: TreeNode?,_ m:inout [Int:Int],_ cnt:inout Int) -> Int31     {32         if node == nil {return 0}33         var left:Int = postorder(node!.left,&cnt)34         var right:Int = postorder(node!.right,&cnt)35         var sum = left + right + node!.val36         if m[sum] == nil37         {38             m[sum] = 139         }40         else41         {42             m[sum]! += 143         }        44         cnt = max(cnt,m[sum]!)45         return sum46     }47 }

64ms

 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 findFrequentTreeSum(_ root: TreeNode?) -> [Int] {16         var result = [Int:Int]()17         _ = _findFrequentTreeSum(root,&result)18         19         let maxRepeat = result.values.max() ?? 020         21         return result.compactMap { key,value in22             guard value == maxRepeat else { return nil }23             return key24         }25     }26     27     func _findFrequentTreeSum(_ root: TreeNode?,28                               _ result: inout [Int:Int]) -> Int 29     {30         guard let root = root else { return 0 }31         32         var value = root.val33         value += _findFrequentTreeSum(root.left,&result)34         value += _findFrequentTreeSum(root.right,&result)35         36         result[value] = (result[value] ?? 0) + 137         38         return value39     }40 }

76ms

 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 findFrequentTreeSum(_ root: TreeNode?) -> [Int] {16         guard let root = root else { return [] }17         18         var counter = [Int : Int]()19         func dfs(_ node: TreeNode?) -> Int {20             guard let node = node else { return 0 }21             let s = node.val + dfs(node.left) + dfs(node.right)22             counter[s,default: 0] += 123             return s24         }25         26         dfs(root)27         let kvs = counter.sorted(by: {$0.1 > $1.1})28         let freq = kvs[0].value29         var ret = [Int]()30         for (s,f) in kvs {31             if f == freq {32                 ret.append(s)33             }34         }35         return ret36     }37 }

84ms

 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     var mp = [Int: Int]()16 17 func postorder(_ root: TreeNode?) -> Int{18     if (root == nil) {19         return 0;20     }21     22     let left = postorder(root?.left);23     let right = postorder(root?.right);24     25     let sum = (root?.val)! + left + right;26     27     if mp[sum] != nil {28         mp[sum]! += 129     } else {30          mp[sum] =  131     }32     return sum;33 }34 35 36 func findFrequentTreeSum(_ root: TreeNode?) -> [Int] {37     postorder(root)38     print(mp)39     var fq = [Int]()40     var max = Int.min41     for number in mp.values {42         if max < number {43             max = number44         }45     }46     47     for (i,number) in mp {48         if max == number {49             fq.append(i)50         }51     }52     53    return fq54   }55 }

104ms

 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 findFrequentTreeSum(_ root: TreeNode?) -> [Int] {16         var map = [Int: Int]()17         traverse(root,&map)18         19         var result = [Int]()20         var max = 021         for (sum,count) in map {22             if count == max {23                 result.append(sum)24             } else if count > max {25                 result.removeAll()26                 max = count27                 result.append(sum)28             }29         }30         return result31     }32     33     private func traverse(_ node: TreeNode?,_ map: inout [Int: Int]) -> Int {34         guard let node = node else { return 0 }35         36         let sum = node.val + traverse(node.left,&map) + traverse(node.right,&map)37         map[sum,default: 0] += 138         39         return sum40     }41 }

108ms

 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 15 class Solution {16     17     func recordSubTreeSums(_ root: TreeNode?,_ subTreeSumMap: inout Dictionary<Int,Int>) -> Int {18         19         guard let node = root else { return 0 }20         21         let subTreeSum =    recordSubTreeSums(node.left,&subTreeSumMap) + 22                             recordSubTreeSums(node.right,&subTreeSumMap) +23                             node.val24         25         if let count = subTreeSumMap[subTreeSum] {26             subTreeSumMap[subTreeSum] = count + 127         } else {28             subTreeSumMap[subTreeSum] = 129         }30         31         return subTreeSum32     }33     34     func findFrequentTreeSum(_ root: TreeNode?) -> [Int] {35         36         var subTreeSumMap:Dictionary<Int,Int> = [:]37         var result:[Int] = []38     39         recordSubTreeSums(root,&subTreeSumMap)40         41         var maxCount = -142         43         for key in subTreeSumMap.keys {44             if let count = subTreeSumMap[key] {45                 if (count > maxCount) { maxCount = count }46             }47         }48         49         for key in subTreeSumMap.keys {50             if let count = subTreeSumMap[key] {51                 if (count == maxCount) { result = result + [key] }52             }53         }54         55         return result56     }57 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode508. 出现次数最多的子树元素和 | Most Frequent Subtree Sum全部内容，希望文章能够帮你解决[Swift]LeetCode508. 出现次数最多的子树元素和 | Most Frequent Subtree Sum所遇到的程序开发问题。

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