首页 > itarticle > lint597. subtree with maximum average

lint597. subtree with maximum average

admin 11月 14, 2020 0

Description

Given a binary tree, find the subtree with maximum average. Return the root of the subtree.

Example

Given a binary tree:

1
2
3
4
5
 
     1
   /   
 -5     11
 /    /  
1   2 4    -2

return the node 11.

> Solve problem here

Thoughts

Let’s first usee DFS recursive with divide and conquer approach. Since average = sum / count, lets creates a new class for return type called ResultType to store both sum and count. 

1
2
3
4
5
6
7
8
 
private class  {
	int sum = 0;
	int count = 0;
	public  (int sum, int count) {
		this.sum = sum;
		this.count = count;
	}
}

Recursive DFS (Divide and Conquer, Bottom-up)

A helper method is also needed since the original method only return TreeNode.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 

 * @param root: the root of binary tree
 * @return: the root of the maximum average of subtree
 */
    
TreeNode maxRoot = null;
private int maxSum = 0;
private int maxCount = 0;
    
public TreeNode findSubtree2(TreeNode root) {
    // write your code here
    // bottom up, (top-down too slow)
    maxRoot = root;
    getSum(root);
    
    return maxRoot;
}
    
public ResultType getSum(TreeNode node) {
    if (node == null) return new ResultType(0, 0);
    
    ResultType left = getSum(node.left);
    ResultType right = getSum(node.right);
    int sum = left.sum + right.sum + node.val;
    int count = left.count + right.count + 1;
    
    // sum / count >? maxSum / maxCount = sum * maxCount ? maxSum * count?
    if (sum * maxCount >= maxSum * count) {
        maxSum = sum;
        maxCount = count;
        maxRoot = node;
    }
    
    return new ResultType(count, sum);
}

Globals can be eliminated by adding them into the input arguements. 

1
2
3
 
public ResultType getSum(TreeNode node, TreeNode maxRoot, ResultType max) {
	...
}

Summary

  • Recursive DFS (Divide and Conquer, Bottom-up)

Logs

  • 02/05/2019: Solution added

Reference

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能