11. ＜ tag binary tree and BST foundation ＞ lt.501 Mode in binary search tree

lt.501. The mode in the binary search tree

[ Case needs ]

[ Train of thought analysis 1 , Violence solution ]

• We can not use BST Characteristics of , Think of it as an ordinary binary tree ,
• The most intuitive solution is to traverse the whole tree , Record all the nodes and frequencies encountered to map In the middle ,
  • namely <Integer, Integer> = < The value of a binary tree node , Frequency of occurrence >
• In addition to map At the same time , We can find the maximum frequency of each node .

The maximum frequency , In us dfs After that , It can be used map.keySet() Ergodic time ,
utilize get(key) == Maximum frequency , Find the number of nodes corresponding to the maximum frequency , Deposit in list Then you can
And then list Convert to array and return ;

[ Code implementation ]

//1.  Violence solution 
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    int maxFreq = 0;

    public int[] findMode(TreeNode root) {
    
        //  The most frequent element 
        //  In the sequence traversal BST It's an ascending sequence 
        //1.  violence ,  use HashMap Record root.val And the number of times  <root.val,  frequency >
        Map<Integer, Integer> map = new HashMap<>();

        //2.  Get the frequency map
        dfs(map, root);

        //3.  Traverse to the maximum frequency and store it in list
        //int count = 1;

        List<Integer> list = new ArrayList<>();
        for(int key : map.keySet()){
    
            // if(count < map.get(key)){
    
            // list.add(key);
            // }else if(list.size() > 0 && count == map.get(key)
            // && key != list.get(list.size() - 1)){
    
            // list.add(key);
            // }
            
            // The purpose is to obtain map in freq maximal ,  If there is an equal maximum ,  Deposit together 
            if(map.get(key) == maxFreq){
    
                list.add(key);
            }
        }

        int[] res = new int[list.size()];
        int index = 0;

        for(int x : list){
    
            res[index++] = x;
        }

        return res;
    }

    public void dfs(Map<Integer, Integer> map, TreeNode root){
    
        //2.  Recursive export 
        if(root == null)return;

        //3.  Single layer recursive logic 
        dfs(map, root.left);

        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        // Get the maximum frequency 
        maxFreq = Math.max(maxFreq, map.getOrDefault(root.val, 0));

        dfs(map, root.right);
    }
}

[ Train of thought analysis II , DFS, utilize BST nature ]

• Remember this sentence : Yes BST In the sequence traversal , What you get is an ascending sequence
• For this question , We use the middle order traversal to get the ascending sequence , Then the repeated numbers are continuous , We just need to record the number corresponding to the maximum number of repetitions .
• Detailed explanation : Am I

[ Code implementation ]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    int maxFreq = 0;
    int count = 0;
    TreeNode pre = null;

    public int[] findMode(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();
        
        dfs(list, root);

        int[] res = new int[list.size()];
        int index = 0;

        for(int x : list){
    
            res[index++] = x;
        }

        return res;
    }

    // In the sequence traversal BST,  Compare the previous node each time , 
    //1.  Same record to count,  Deposit... At a different time next time list;
    //2. 
    
    public void dfs(List<Integer> list, TreeNode root){
    
        //1.  Recursion end condition 
        if(root == null)return;

        dfs(list, root.left); 

        //1.  Record the possible modes 
        if(pre == null || pre.val == root.val){
    
            ++count;
        }else{
    
            count = 1;
        }

        //2.  Add a large mode to list,
        //  If you meet a bigger ,  Empty list,  To add 
        if(count == maxFreq){
    
            list.add(root.val);
        }else if(count > maxFreq){
    
            maxFreq = count;
            list.clear();
            list.add(root.val);
        }
        pre = root;

        dfs(list,root.right);
    }
}