Description

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

tree

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

DFS using HashMap, time O(n), space O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> valToCount = new HashMap<>();
        int maxCount = findModeHelper(root, valToCount, 0);

        List<Integer> modeList = new LinkedList<>();
        for (int val : valToCount.keySet()) {
            if (valToCount.get(val) == maxCount) {
                modeList.add(val);
            }
        }
        
        int[] modes = new int[modeList.size()];
        for (int i = 0; i < modes.length; ++i) {
            modes[i] = modeList.get(i);
        }
        
        return modes;
    }
    
    public int findModeHelper(TreeNode root, Map<Integer, Integer> map, int max) {
        if (root == null) {
            return max;
        }
        
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        max = Math.max(max, map.get(root.val));
        
        return Math.max(findModeHelper(root.left, map, max)
                       , findModeHelper(root.right, map, max));
    }
}

DFS, time O(n), space O(1)

对于BST来说，中序遍历的结果是递增的。所以此题目转换成求一个递增数组中出现次数最多的数字。

可以用Morris中序遍历，第一遍遍历保存maxCount和modeCount，第二遍遍历再填充返回值。懒得写了。。（其实不会写哈哈）