1120.Subtree with Maximum Average

Lintcode 597

1.Description(Easy)

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

Example

Given a binary tree:

     1
   /   \
 -5     11
 / \   /  \
1   2 4    -2

return the node11.

2.Code

加一个HelperType记录当前的sum和size

两个类变量 currentData记录最大的average 和 currentNode记录最大值的节点。

divided conquer

每次比较当前平均值和currentData中的平均值的大小，大的话就覆盖

private class HelperType{
        public int sum;
        public int size;
        public HelperType(int sum,int size){
            this.size=size;
            this.sum=sum;
        }
    }

    public TreeNode currentNode=null;
    public HelperType currentData=null;

    public HelperType helper(TreeNode root){
        if(root==null){
            return new HelperType(0,0);
        }
        HelperType left=helper(root.left);
        HelperType right=helper(root.right);
        HelperType result=new HelperType(root.val+left.sum+right.sum,1+left.size+right.size);
        if(currentNode==null){
            currentNode=root;
            currentData=result;
        }
        if(currentData.size*result.sum>currentData.sum*result.size){
              currentData=result;
              currentNode=root;
        }
        return result;
    }
    public TreeNode findSubtree2(TreeNode root){
        helper(root);
        return currentNode;
    }

public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the root of the maximum average of subtree
     */

    private TreeNode maxNode = null;
    private Node currentNode = null;

    public TreeNode findSubtree2(TreeNode root) {
        // write your code here
        postOrderTraverse(root);
        return maxNode;
    }

    public Node postOrderTraverse(TreeNode root)
    {
        if(root == null) return new Node(0,0);
        Node left = postOrderTraverse(root.left);
        Node right = postOrderTraverse(root.right);

        Node result = new Node(left.sum + right.sum + root.val, left.count+right.count+1);
        if(maxNode == null)
        {
            maxNode = root;
            currentNode = result;
        }
        // compare currentNode and result
        if(currentNode.sum*result.count < result.sum*currentNode.count)
        {
            maxNode = root;
            currentNode = result;
        }
        return result;
    }
}

class Node
{
     int sum;
     int count;
     Node(int sum, int count)
    {
        this.sum = sum;
        this.count = count;
    }
}