Leetcode - Maximum Average Subtree

https://leetcode.com/problems/maximum-average-subtree/

Given the root of a binary tree, find the maximum average value of any subtree of that tree.

(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)

Example 1:

Input: [5,6,1]
Output: 6.00000

1. Define a tree struct which contains a sum to sum all nodes in subtree and a count to count all nodes in subtree

2. Create a new tree use defined tree struct from the original tree

3. Loop in the new tree and find the max average

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type MyTree struct {
    Val int
    Sum int
    Count int
    Left *MyTree
    Right *MyTree
}

func maximumAverageSubtree(root *TreeNode) float64 {
    myRoot := sumTree(root)
    queue := []*MyTree{myRoot}
    max := float64(0)
    for len(queue) != 0 {
        node := queue[0]
        queue = queue[1:]
        if node != nil {
            if float64(node.Sum) / float64(node.Count) > max {
                max = float64(node.Sum) / float64(node.Count)
            }
            queue = append(queue, node.Left)
            queue = append(queue, node.Right)
        }
    }
    return max
}

func sumTree(root *TreeNode) (*MyTree) {
    if root == nil {
        return nil
    }
    if root.Left == nil && root.Right == nil {
        return &MyTree{Val: root.Val, Count: 1, Sum: root.Val}
    }
    
    left := sumTree(root.Left)
    right := sumTree(root.Right)
    var sum int
    var count int
    if left != nil {
        sum += left.Sum
        count += left.Count
    }
    if right != nil {
        sum += right.Sum
        count += right.Count
    }
    
    node := &MyTree{
        Sum: root.Val + sum,
        Count: count + 1,
        Val: root.Val,
        Left: left,
        Right: right,
    }
    
    return node
}

• 相关文章
• 全局相关文章