LC501. 二叉搜索树中的众数

暴力计算众数，空间复杂度O(N)，因为用了一个数组存储中序遍历的结果
之后就是有序数组求众数了，这其实没有用到二叉搜索树的特性。

class Solution(object):
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        sol = []
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(root)
        d = collections.defaultdict(int) #用一个字典统计各个元素的数量
        for i in res:
            d[i] += 1
        x = sorted(d.values())
        max = x[-1]                      #获取最多的那个元素
        for i in d.items():
            if i[1] == max:
                sol.append(i[0])         #将对应的键加入答案
        return sol
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

空间复杂度O（1）的方法

def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.count = 0
        self.maxcount = 0
        self.res = []
        self.pre = None
        def inorder(root):
            if not root:
                return 
            inorder(root.left)   #利用中序是有序的性质，在中序位置加入处理逻辑
            if self.pre == None:
                self.count = 1
            elif root.val == self.pre.val:
                self.count += 1
            else:
                self.count = 1
            self.pre = root
            if self.count == self.maxcount: #等于的时候不能置空，所以要加上这一句
                self.res.append(root.val)
            if self.count > self.maxcount:  #大于的时候就需要换，所以需要置空并且重新append
                self.maxcount = self.count
                self.res = []
                self.res.append(root.val)
            inorder(root.right)
        inorder(root)
        return self.res
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