Given a binary search tree (BST) with duplicates, find all the  (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).

 

M1: using extra space

traverse的时候，用hashmap存每个节点出现的次数

time: O(n), space: O(n)

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    int max = 0;        public int[] findMode(TreeNode root) {        if(root == null) {            return new int[] {};        }        Map
     
       map = new HashMap<>();        traverse(root, map);                List
      
        tmp = new ArrayList<>();        for(Map.Entry
       
         entry : map.entrySet()) {            if(entry.getValue() == max) {                tmp.add(entry.getKey());            }        }                int[] res = new int[tmp.size()];        for(int i = 0; i < tmp.size(); i++) {            res[i] = tmp.get(i);        }        return res;    }        public void traverse(TreeNode root, Map
        
          map) {        if(root == null) {            return;        }        map.put(root.val, map.getOrDefault(root.val, 0) + 1);        max = Math.max(max, map.get(root.val));        traverse(root.left, map);        traverse(root.right, map);    }}
        
       
      
     

 

M2: optimized, not using extra space