FindModeInBinarySearchTree [source code]

public class FindModeInBinarySearchTree {
static
/******************************************************************************/
public class Solution {
    public int[] findMode(TreeNode root) {
        List<Integer> resLs = new ArrayList<>();
        if (root == null) return new int[0];
        Map<Integer, Integer> counts = new HashMap<>();
        dfs(counts, root);
        int max = 0;
        for (Map.Entry e : counts.entrySet()) {
            int value = (Integer) e.getValue();
            int key = (Integer) e.getKey();
            if (value > max) {
                resLs.clear();
                max = value;
                resLs.add(key);
            } else if (value == max) {
                resLs.add(key);
            }
        }
        int[] res = new int[resLs.size()];
        int end = 0;
        for (int i : resLs) res[end++] = i;
        return res;
    }

    private void dfs(Map<Integer, Integer> counts, TreeNode root) {
        if (root == null) return;
        Integer count = counts.get(root.val);
        if (count == null) {
            counts.put(root.val, 1);
        } else {
            counts.put(root.val, count + 1);
        }
        dfs(counts, root.left);
        dfs(counts, root.right);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindModeInBinarySearchTree.Solution tester = new FindModeInBinarySearchTree.Solution();
    }
}

这个算法是非常 naive 的写法, 就是把 tree 当做是普通的 array 来做而已, 完全无视 tree 本身的特性, 尤其是 BST 的特性; 纯粹用 DFS 来iterate 走一遍, 然后把所有的 count 再过一遍看看结果就行了; 最后的速度是17ms (29%), 不算出色;

Problem 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],
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).

Difficulty:Easy
Category:Algorithms
Acceptance:37.96%
Contributor: Coder_1215
Companies
google
Related Topics
tree
Similar Questions
Validate Binary Search Tree