[Swift]LeetCode501.二叉搜索树中的众数|FindModeinBinarySearchTree

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9807156.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

For example:

Given BST [1,null,2,2],

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

例如：
给定 BST [1,null,2,2],

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

40ms

 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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {    
15     func findMode(_ root: TreeNode?) -> [Int] {
16         var prev: TreeNode?
17         var result: [Int] = []
18         var count = 1
19         var max = 0
20         
21         inorder(root, &prev, &result, &count, &max)
22         
23         return result
24     }
25     
26     func inorder(_ node: TreeNode?, _ prev: inout TreeNode?, _ result: inout [Int], _ count: inout Int, _ max: inout Int) {
27         guard let node = node else {
28             return
29         }
30         
31         inorder(node.left, &prev, &result, &count, &max)
32         
33         if let prev = prev, prev.val == node.val {
34             count += 1
35         } else {
36             count = 1
37         }
38         
39         if count >= max {
40             if count > max {
41                 max = count
42                 result.removeAll()
43             }
44             
45             result.append(node.val)
46         }
47         
48         prev = node
49         
50         inorder(node.right, &prev, &result, &count, &max)
51     }
52 }

44ms

 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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15   private var prev: TreeNode? = nil
16   private var modes = [Int]()
17   private var countMode = 0
18   private var countTemp = 0
19 
20   func findMode(_ root: TreeNode?) -> [Int] {
21     guard let node = root else { return modes }
22     findMode(node.left)
23     visitNode(node)
24     findMode(node.right)
25     return modes
26   }
27 
28   private func visitNode(_ root: TreeNode) {
29     defer { prev = root }
30 
31     guard let prev = prev else {
32       if modes.isEmpty {
33         modes = [root.val]
34         countTemp = 1
35         countMode = countTemp
36       }
37       return
38     }
39 
40     countTemp = prev.val == root.val ? countTemp + 1 : 1
41 
42     if countTemp == countMode {
43       modes += [root.val]
44     } else if countMode < countTemp {
45       countMode = countTemp
46       modes = [root.val]
47     }
48   }
49 }

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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func findMode(_ root: TreeNode?) -> [Int] {
16         var maxNumCount = 0
17         var currentNum: Int?
18         var currentNumCount: Int?
19         var modes = [Int]()
20         inorderTraversal(root, &maxNumCount, &currentNum, &currentNumCount, &modes)
21         return modes
22     }
23     
24     func inorderTraversal(_ root: TreeNode?, _ maxNumCount: inout Int, _ currentNum: inout Int?, _ currentNumCount: inout Int?, _ modes: inout [Int]) {
25         guard let root = root else {
26             return
27         }
28         inorderTraversal(root.left, &maxNumCount, &currentNum, &currentNumCount, &modes)
29         if root.val == currentNum {
30             currentNumCount! += 1
31         } else {
32             currentNum = root.val
33             currentNumCount = 1
34         }
35         if currentNumCount! > maxNumCount {
36             maxNumCount = currentNumCount!
37             modes = [root.val]
38         } else if currentNumCount! == maxNumCount {
39             modes.append(root.val)
40         }
41         inorderTraversal(root.right, &maxNumCount, &currentNum, &currentNumCount, &modes)
42     }
43 }

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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15 
16   var maxFrequency = 0
17   var maxCounter = 0
18 
19   var lastValue: Int? = nil
20   var lastFrequency = 0
21 
22   var result = [Int]()
23   var resultIndex = 0
24 
25   func findMaxFrequency(_ root: TreeNode?) {
26     if (root == nil) { return }
27     
28     findMaxFrequency(root?.left)
29     
30     if(lastValue == nil || root?.val != lastValue) {
31       lastFrequency = 1
32     } else {
33       lastFrequency += 1
34     }
35     
36     if(maxFrequency < lastFrequency) {
37       maxFrequency = lastFrequency
38       maxCounter = 1
39     } else if (maxFrequency == lastFrequency) {
40       maxCounter += 1
41     }
42     
43     lastValue = root?.val
44     
45     findMaxFrequency(root?.right)
46   }
47 
48   func fillValues(_ root: TreeNode?) {
49     if (root == nil) { return }
50 
51     fillValues(root?.left)
52 
53     if(lastValue == nil || root?.val != lastValue) {
54       lastFrequency = 1
55     } else {
56       lastFrequency += 1
57     }
58 
59     if(lastFrequency == maxFrequency) {
60       resultIndex += 1
61       if result.count > resultIndex-1 {
62         result[resultIndex-1] = root?.val ?? 0
63       }
64     }
65 
66     lastValue = root?.val
67 
68     fillValues(root?.right)
69   }
70 
71   func findMode(_ root: TreeNode?) -> [Int] {
72     findMaxFrequency(root)
73     
74     result = [Int](repeating: 0, count: maxCounter)
75     lastValue = nil
76     fillValues(root)
77 
78     return result
79   }
80 }

96ms

 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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     //记录当前的“可能的众数”节点值
16     var pre:Int? = nil
17     //记录当前“确定的众数”出现的次数
18     var maxTimes = 0 
19     //记录“可能的众数”出现的次数
20     var count:Int = 1
21     func findMode(_ root: TreeNode?) -> [Int] {
22         if root == nil {return [Int]()}
23         var list:[Int] = [Int]()
24         dfs(root,&list)
25         
26         let len = list.count
27         var res:[Int] = Array(repeating: 0,count:len)
28         for i in 0..<len
29         {
30             res[i] = list[i]
31         }
32         return res      
33     }
34     func dfs(_ node: TreeNode?,_ list: inout [Int])
35     {
36         if node == nil {return}
37         dfs(node!.left,&list)
38         if pre != nil
39         {
40            if node!.val == pre
41             {
42                 count += 1
43             }
44             else
45             {
46                 count = 1
47             }
48         }
49         if count > maxTimes
50         {
51             //清空数组
52             list = [Int]()
53             list.append(node!.val)
54             maxTimes = count
55         }
56         else if count == maxTimes
57         {
58            list.append(node!.val)
59         }
60         pre = node!.val
61         dfs(node!.right,&list) 
62     }
63 }