gogoWebsite

background

It caused me to think about the problem of Map sorting in Java, which is fromLeetCode 501. Binary search mode in the tree.

This question requires that the value that appears the most in the node in the tree based on a given binary search tree, and is not unique. In other words, it means searching for modes in the tree, and not unique.

idea

When you see this question, you first think of traversing each node in the entire tree, and at the same time save the median value of the node (because the value you want to return in the end) and its number of occurrences.

Then the first thing you want to use to save paired data is the Map data structure, Key saves node value, and Value saves value appear. Then iterate over the tree and save the frequency of occurrence. It is not difficult to achieve this. Just use the function to store the key and value and set the value of the value with the function. The code is as follows:

public void traversal(TreeNode root) {
    //Use the pre-order traversal, and save its value and its frequency of occurrence when encountering a node.
    map.put(root.val, map.getOrDefault(root.val, 0) + 1);
    //put(key, value): deposit key and its value at the same time
    //getOrDefault(key, defaultValue): If there is no such value, let its value (i.e., the number of occurrences) be defaultValue; if there is this value, then get its value (i.e., the number of occurrences)
    // Since the default value should be 1, but considering that there is a value, you need to add 1, so the default value is set to zero, and the operation is unified
    
    if (root.left != null) traversal(root.left);//Travel the left subtree
    if (root.right != null) traversal(root.right);//Travel the right subtree
}

At present, the node values ​​and their frequency of occurrence in the tree have been obtained. However, the question is, how to find out the mode in the map?

The most direct idea is to sort maps (although it is unnecessary, but you have to do this, which is just stubborn). So how to sort maps? There are two methods.

Method 1: List +

I have checked all the information and said that I first create a list to save the key-value pair in the Map (save it using entrySet in the Map), and then use the sort function in the Collections interface to realize the Map sorting. The code is as follows:

//Create a list to save the key-value pair in the map, and obtain the key-value pair in the map through()
List<Map.Entry<Integer,Integer>> list = new LinkedList<>(map.entrySet());

//Use the sort function of the Collections interface to sort the list in descending order, and the Comparator interface comparison method needs to be implemented
Collections.sort(list, new Comparator(){
    public int compare(Object o1, Object o2){
		//Comparable method in Comparable interface
		//(B): A > B returns a positive integer; A < B returns a negative integer; equal, return 0
		
		//Comparer method in Comparator interface
		//Return positive integer: ascending order; return negative integer: descending order
        return -((Comparable)((Map.Entry)(o1)).getValue()).compareTo(((Map.Entry)(o2)).getValue());
    }
});

At this point, the list has been sorted, just traverse the list and save it into the map. The code is as follows:

//Save the sorted <key, value> pair in the list and put it into the map
map.clear();
for (Map.Entry<Integer, Integer> entry : list) {
    map.put(entry.getKey(), entry.getValue());
}

Method 2: PriorityQueue (recommended)

After we have obtained the Map, we can arrange the Keys in descending order according to the Value value in the Map by the following method.

// 1. Define the priority queue (essentially a large top heap)
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());

// 2. Put elements in the Map into the priority queue and will be automatically sorted in descending order according to the Value value.
for (Map.Entry<Integer, Integer>> entry : map.entrySet()) {
	pq.offer(entry);
}

// 3. At this time, the top element of the pile is the mode
int modeNumber = pq.poll().getKey();