Find the mode in the binary search tree (use medium order traversal as an ordered array)

501. The mode in the binary search tree

The difficulty is simple

Give you a binary search tree with duplicate values （BST） The root node root , Find out and return to BST All in The number of （ namely , The most frequent element ）.

If there is more than one mode in the tree , Can press In any order return .

Assume BST Meet the following definitions ：

• The value of the node contained in the left subtree of the node Less than or equal to The value of the current node
• The value of the node contained in the right subtree of the node Greater than or equal to The value of the current node
• Both the left and right subtrees are binary search trees

Ideas

The definition here is similar to what we usually encounter BST The definition of is different , Therefore, it should be clear that values equal to the current node may appear in both the left subtree and the right subtree , So it is very difficult to deal with recursion alone

But I am As mentioned in a previous question , Traverse the binary search tree , What you get is an ordered array .

Find the mode on an ordered array , Isn't it easy to catch ？

If you really don't understand it, you can go through the middle order first and add all the elements to an array , Then find the mode on the array

Of course, it is not recommended , This will lead to low time efficiency

package cn.edu.xjtu.carlWay.tree.findModeInBST;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/** * 501.  The mode in the binary search tree  *  Give you a binary search tree with duplicate values （BST） The root node  root , Find out and return to  BST  All in   The number of （ namely , The most frequent element ）. * <p> *  If there is more than one mode in the tree , Can press   In any order   return . * <p> *  Assume  BST  Meet the following definitions ： * <p> *  The value of the node contained in the left subtree of the node   Less than or equal to   The value of the current node  *  The value of the node contained in the right subtree of the node   Greater than or equal to   The value of the current node  *  Both the left and right subtrees are binary search trees  * <p> * https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/ */
public class Solution {
    
    List<Integer> result = new ArrayList<>();
    int maxNum = 0;
    TreeNode pre;
    int count = 0;

    public int[] findMode(TreeNode root) {
    
        if (root == null) return null;
        traversal(root);
        int[] ret = new int[result.size()];
        for (int i = 0; i < ret.length; i++) {
    
            ret[i] = result.get(i);
        }
        return ret;
    }

    private void traversal(TreeNode root) {
    
        if (root == null) return;
        //  Recursive left subtree 
        traversal(root.left);

        //  Processing data 
        if (pre == null || root.val != pre.val) {
    
            count = 1;
        } else {
    
            count++;
        }

        if (count > maxNum) {
    
            result.clear();
            result.add(root.val);
            maxNum = count;
        } else if (count == maxNum) {
    
            result.add(root.val);
        }

        pre = root;

        //  Recursive right subtree 
        traversal(root.right);
    }
}