Subject to introduce

Buckle 501: leetcode-cn.com/problems/fi…

Method: order traversal

Ideas and Algorithms

First of all we can think of one of the most simple approach: because this tree is an ordered sequence traversal sequence, so we can get sequence traversal of the tree, and then from scanning the sequence traversal sequence, and then use a hash table to count every number number, so that you can find the Numbers appear most times. But the spatial complexity of doing this is obviously not O(1), because the spatial cost of both hash tables and sequential traversal sequences in storage is O(n).

First, let’s consider not using a hash table when looking for the most frequent occurrences. This optimization is based on the property of order traversal in binary search trees: the middle order traversal of a binary search tree is a non-decreasing ordered sequence. Such as:

The middle-order traversal sequence of such a binary search tree is {−1,0,0,1,2,2}. We can see that repeated numbers must be consecutive, for example, 0 and 2 here, they are repeated, and all the 0’s are concentrated in a continuous segment, and all the 2’s are concentrated in a continuous segment. We can use base to record the current number, count to record the number of repeats, maxCount to maintain the number of occurrences of the number that has been scanned the most, and use the answer array to record the mode. Each time a new element is scanned:

  • First update base and count:
    • If the element is equal to base, count increments by one;
    • Otherwise, update base to the current number and reset count to 1.
  • Then update maxCount:
    • If count=maxCount, then the number of occurrences of base is equal to the number of occurrences of mode. Add base to answer array;
    • If count > maxCount, it means that the current number base appears more times than the current mode. Therefore, we need to update maxCount to count and add base to the answer array after clearing the answer array.

We can write this as an update function. So we can save a hash table on the space we need to find the most common number.

Then, we consider not storing the middle-order traversal sequence. If we use the update function above to access a certain point in the recursive order traversal, we can save space for the order traversal sequence, as follows.

class Solution {
    List<Integer> answer = new ArrayList<Integer>();
    Count counts the number of occurrences of the current node value. MaxCount stores the number of occurrences of the node value
    int base, count, maxCount;

    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode;
    }

    public void dfs(TreeNode o) {
        if (o == null) {
            return;
        }
        dfs(o.left);
        update(o.val);
        dfs(o.right);
    }

    public void update(int x) {
        // The number of times the current node value is updated as the last accessed node value
        if (x == base) {
            ++count;
        } else {
            //// The value of the current node is different from the value of the last accessed node. The number of times the value of this node is updated is 1
            count = 1;
            base = x;
        }
        // If the number of occurrences of the current node value equals the maximum number of occurrences so far, the node value is added to the result list
        if (count == maxCount) {
            answer.add(base);
        }
        
        // If the number of occurrences of the current node value is greater than the current maximum, the previous result list is cleared
        if(count > maxCount) { maxCount = count; answer.clear(); answer.add(base); }}}Copy the code

Complexity analysis

  • Time complexity: O(n). The complexity of traversing the tree.
  • Space complexity: O(n). The space cost of recursive stack space.