LeetCode : 501. Find Mode in Binary Search Tree

[congr]

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

[congr]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> map = new HashMap();

        List<Integer> list = new ArrayList();
        preorder(root, map);
        for (int key : map.keySet()) {
            if (map.get(key) == max) list.add(key);
        }

        int[] res = new int[list.size()];
        int i = 0;
        for (int n : list) res[i++] = n;
        return res;
     }

    int max;
    void preorder(TreeNode root, Map<Integer, Integer> map) {
        if (root == null) return;

        max = Math.max(max, map.merge(root.val, 1, Integer::sum));
        preorder(root.left, map);
        preorder(root.right, map);
    }
}