Find Mode in Binary Search Tree-二叉搜索树中的众数

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).

Solution in python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        adic = dict()
        def traverse(root):
            if root == None:
                return 
            else:
                traverse(root.left)
                if root.val not in adic.keys():
                    adic[root.val] = 1
                else:
                    adic[root.val] += 1
                traverse(root.right)
        traverse(root)
        result = []
        if not adic:
            return result
        max_value = max(adic.values())
        for key in adic.keys():
            if adic[key] == max_value:
                result.append(key)
        return result