Problem

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

   1
    
     2
    /
   2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution

class Solution {
    int count = 0;
    int maxCount = 0;
    Integer pre = null;
    public int[] findMode(TreeNode root) {
        List<Integer> resList = new ArrayList<>();
        helper(root, resList);
        return resList.stream().mapToInt(i->i).toArray();
    }
    private void helper(TreeNode root, List<Integer> res) {
        if (root == null) return;
        helper(root.left, res);
        if (pre == null) {
            pre = root.val;
            count = 1;
            maxCount = 1;
            res.add(root.val);
        } else {
            if (root.val == pre) {
                count++;
                if (count > maxCount) {
                    res.clear();
                    maxCount = count;
                }
            } else {
                pre = root.val;
                count = 1;
            }
            if (count == maxCount) {
                res.add(root.val);
            }
        }
        helper(root.right, res);
    }
}