501. 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],

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

# 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):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        dic = {}
        def inorder(root):
            if root.left:
                inorder(root.left)
            if root.val not in dic:
                dic[root.val] = 1
            else:
                dic[root.val] += 1
            if root.right:
                inorder(root.right)
        inorder(root)
        # print(dic)
        m = max(dic.values())
        # print(m)
        res = []
        for key,value in dic.items():
            # print(key,value)
            if value==m:
                res.append(key)
        return res