Leetcode skimming: binary tree 23 (mode in binary search tree)

501. The mode in the binary search tree

Force button topic link

Given a binary search tree with the same value （BST）, find BST All the modes in （ The most frequent element ）.

Assume BST It has the following definition ：

• The value of the node contained in the left subtree of a node is less than or equal to the value of the current node
• The value of the node contained in the right subtree of a node is greater than or equal to the value of the current node
• Both the left and right subtrees are binary search trees

for example ：

Given BST [1,null,2,2],

return [2].

Tips ： If the mode exceeds 1 individual , There is no need to consider the output sequence

Advanced ： Can you not use extra space ？（ Suppose the overhead of implicit call stack generated by recursion is not counted ）

Two ways of thinking ：

1: General writing method , Hashtable , Traversing the tree , Save the result set to hashmap, Traversal frequency value Get the maximum , Iterate again to get the result set , Process into an array .

 HashMap<Integer, Integer> result = new HashMap<Integer, Integer>();

    public int[] findMode(TreeNode root) {
    
        // This problem can be done with a hash table 
        traversal(root);
        Set<Integer> keys = result.keySet();
        int max = -1;
        for (Integer key : keys) {
    
            if (result.get(key) > max) {
    
                max = result.get(key);
            }
        }
        Set<Integer> resultSet = new HashSet<Integer>();
        for (Integer key : keys) {
    
            if (result.get(key) == max) {
    
                resultSet.add(key);
            }
        }
        int[] resultArr = new int[resultSet.size()];
        int index = 0;
        for (Integer key : resultSet) {
    
            resultArr[index] = key;
            index++;
        }
        return resultArr;
    }

    public void traversal(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        traversal(root.left);
        if (result.containsKey(root.val)) {
    
            result.put(root.val, result.get(root.val) + 1);
        } else {
    
            result.put(root.val, 1);
        }
        traversal(root.right);
    }

2. Binary search tree writing ： Because it's a binary search tree , The decreasing , So the same number must be together , Count the number of occurrences of each number , Give a maximum number of occurrences , If the number of occurrences of the current number is less than the maximum number , Do not change , If equal , Then add the current number to the result set , If it is greater than the maximum number of occurrences , Then empty the result set , The current number is added to the result set .

  List<Integer> list = new ArrayList<>();
    TreeNode parent;
    int maxTimes = 0;
    int curTimes = 0;

    public void inorderTraversal(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        inorderTraversal(root.left);
        if (root.val == parent.val) {
    
            curTimes++;
            // If the number of occurrences of the current element is greater than the maximum number , Then a new mode appears , The original is not the mode 
            if (curTimes > maxTimes) {
    
                maxTimes = curTimes;
                list.clear();
                list.add(root.val);
            } else if (curTimes == maxTimes) {
    
                // If the number of occurrences of the current element is equal to the maximum number , Then a new mode appears 
                list.add(root.val);
            }
        } else {
    
            curTimes = 1;
                      if (curTimes > maxTimes) {
    
                maxTimes = curTimes;
                list.clear();
                list.add(root.val);
            } else if (curTimes == maxTimes) {
    
                // If the number of occurrences of the current element is equal to the maximum number , Then a new mode appears 
                list.add(root.val);
            }
            parent = root;
        }
        inorderTraversal(root.right);
    }


    public int[] findMode(TreeNode root) {
    
        parent = root;
        inorderTraversal(root);
        int index = 0;
        int[] resultArr = new int[list.size()];
        for (Integer result : list) {
    
            resultArr[index] = result;
            index++;
        }
        return resultArr;
    }