LC501. Mode in binary search tree

Violent calculation mode , Spatial complexity O(N), Because an array is used to store the results of the middle order traversal
Then it is the ordered array to find the mode , In fact, this does not use the characteristics of binary search tree .

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) # Count the number of each element with a dictionary 
        for i in res:
            d[i] += 1
        x = sorted(d.values())
        max = x[-1]                      # Get the most elements 
        for i in d.items():
            if i[1] == max:
                sol.append(i[0])         # Add the corresponding key to the answer 
        return sol

Spatial complexity O（1） Methods

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)   # Using the property that middle order is order , Add processing logic in the middle order 
            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: # Cannot be empty when equal to , So add this sentence 
                self.res.append(root.val)
            if self.count > self.maxcount:  # When it is larger than, it needs to be changed , So you need to empty it and re append
                self.maxcount = self.count
                self.res = []
                self.res.append(root.val)
            inorder(root.right)
        inorder(root)
        return self.res