LeetCode 508. Most Frequent Subtree Sum

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/02/08/LeetCode-508-Most-Frequent-Subtree-Sum/

访问原文「LeetCode 508. Most Frequent Subtree Sum」

题目要求

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1
Input:

5
/ \
2 -3
return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2
Input:

5
/ \
2 -5
return [2], since 2 happens twice, however -5 only occur once.

题意解析

子树和的含义是指树中的一个节点所有子节点值得和（包含该节点）。一棵树每个节点都有子树和，找到存在数目最多的子树和。

解法分析

这道题的主要解法就是递归了，没给节点的子树和等于该节点的值加上左子树的子树和和右子树的子树和。最后在统计出最多的子树和就可以了。

解题代码

public int[] findFrequentTreeSum(TreeNode root) {
  	if(root == null){
  		return new int[]{};
  	}
  	
  	Map<Integer, Integer> sumMap = new HashMap<>();
  	
  	int rootSum = calcSubTreeSum(sumMap, root);
  	
int maxSum = Integer.MIN_VALUE;
int resultNumber = 0;
for(int num : sumMap.keySet()){
	if(sumMap.get(num) > maxSum){
		maxSum = sumMap.get(num);
		resultNumber = 1;
	}else if(sumMap.get(num) == maxSum){
		resultNumber ++;
	}
}

int[] results = new int[resultNumber];
int i = 0;
for(int num : sumMap.keySet()){
	if(sumMap.get(num) == maxSum){
		results[i++] = num;
	}
}

return results;
  }
  
  private int calcSubTreeSum(Map<Integer, Integer> sumMap, TreeNode root){
  	if(root.left == null && root.right == null){
  		sumMap.put(root.val, sumMap.getOrDefault(root.val, 0) + 1);
  		return root.val;
  	}
  	int left = 0;
  	int right = 0;
  	if(root.left != null){
  		left = calcSubTreeSum(sumMap, root.left);
  	}

  	if(root.right != null){
  		right = calcSubTreeSum(sumMap, root.right);
  	}
  	
  	int curSum = root.val + left + right;
  	sumMap.put(curSum, sumMap.getOrDefault(curSum, 0) + 1);
  	
  	return curSum;
  }