Java traversal the tree once with two map


  • 0
    D
    class Solution {
    	int maxtimes = 0;
    	public int[] findFrequentTreeSum(TreeNode root) {
    		if (root == null) {
    			return new int[0];
    		}
    		Map<Integer,Integer> times = new HashMap<>();
    		Map<Integer,Set<Integer>> tvals = new HashMap<>();
    		updateNodeValue(root, times, tvals);
    		Set<Integer> vals = tvals.get(maxtimes);
    		int[] rs = new int[vals.size()];
    		int i = 0;
    		for (int v : vals) {
    			rs[i++] = v;
    		}
    		return rs;
    	}
    
    	private int updateNodeValue(TreeNode node, Map<Integer,Integer> map, Map<Integer, Set<Integer>> tvals) {
    		if (node == null) {
    			return 0;
    		}
    		node.val += updateNodeValue(node.left, map, tvals) + updateNodeValue(node.right, map, tvals);
    		if (!map.containsKey(node.val)) {
    			map.put(node.val, 0);
    		} else {
          Set<Integer> set = tvals.get(map.get(node.val));
    			set.remove(node.val);
    			if (set.isEmpty()) {
    				tvals.remove(map.get(node.val));
    			}
    		}
    		map.put(node.val, map.get(node.val) + 1);
    		int time = map.get(node.val);
    		if (!tvals.containsKey(time)) {
    			tvals.put(time, new HashSet<Integer>());
    		}
    		tvals.get(time).add(node.val);
    		if (map.get(node.val) > maxtimes) {
    			maxtimes = map.get(node.val);
    		}
    		return node.val;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.