501. 二叉搜索树中的众数

501. 二叉搜索树中的众数

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        self.mode = []
        self.curCount = 0
        self.maxCount = 0
        self.prev = None
        self.traverse(root)
        return self.mode 
    
    def traverse(self, root):
        if not root:
            return

        self.traverse(root.left)

        if not self.prev:
            self.curCount = 1
            self.maxCount = 1
            self.mode.append(root.val)
        else:

            if root.val == self.prev.val:
                self.curCount += 1
                # root.val 是众数
                if self.curCount == self.maxCount:
                    self.mode.append(root.val)
                elif self.curCount > self.maxCount:
                    # 更新众数
                    self.mode.clear()
                    self.maxCount = self.curCount
                    self.mode.append(root.val)

            if root.val != self.prev.val:
                # root.val 不重复的情况
                self.curCount = 1
                if self.curCount == self.maxCount:
                    self.mode.append(root.val)

        # 更新prev 
        self.prev = root
        self.traverse(root.right)


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50