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
3
4
5
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).

思路

如果利用额外的存储空间，只需要遍历二叉搜索树即可；利用哈希表对字符出现的个数进行统计。

如果严格利用O(1)的存储空间，需要遍历两次二叉树；第一次找到众数(mode)的数字，第二次找到符合众数个数的字符。而且如果采用非递归的方法会更佳。这里可以利用[Morris Traversal][http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html]的方法来实现。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        count = {}
        if (root):
            self.helper(root, count)
            maxval = max(count.values())
        else:
            maxval = 0
        
        for i in count:
            if count[i] == maxval:
                result.append(i)
        return result
        
    def helper(self, root, count):
        if count.has_key(root.val):
            count[root.val] += 1
        else:
            count[root.val] = 1
        
        if (root.left):
            self.helper(root.left, count)
        if (root.right):
            self.helper(root.right, count)
        
        return count