2021-11-28:有一棵树,给定头节点h,和结构数组m,下标0弃而不用。 比如h = 1, m = [ [] , [2,3], [4], [5,6], [], [], []], 表示1的孩子是2、3; 2的孩子是4; 3的孩子是5、6; 4、5和6是叶节点,都不再有孩子, 每一个节点都有颜色,记录在c数组里,比如c[i] = 4, 表示节点i的颜色为4, 一开始只有叶节点是有权值的,记录在w数组里, 比如,如果一开始就有w[i] = 3, 表示节点i是叶节点、且权值是3。 现在规定非叶节点i的权值计算方式: 根据i的所有直接孩子来计算,假设i的所有直接孩子,颜色只有a,b,k。 w[i] = Max { (颜色为a的所有孩子个数 + 颜色为a的孩子权值之和), (颜色为b的所有孩子个数 + 颜色为b的孩子权值之和), (颜色为k的所有孩子个数 + 颜色k的孩子权值之和) } 请计算所有孩子的权值并返回。 来自美团。

答案2021-11-28:

这道题考的是语文。后序遍历。 当前来到h节点, h的直接孩子,在哪呢?m[h] = {a,b,c,d,e}, 每个节点的颜色在哪?比如i号节点,c[i]就是i号节点的颜色, 每个节点的权值在哪?比如i号节点,w[i]就是i号节点的权值, void : 把w数组填满就是这个函数的目标。

代码用golang编写。代码如下:

package main

import "fmt"

func main() {
    h := 1
    m := [][]int{{}, {2, 3}, {4}, {5, 6}, {}, {}, {}}
    w := []int{0, 0, 0, 4, 5, 6, 0}
    c := []int{0, 0, 0, 4, 3, 2, 0}
    w0(h, m, w, c)
    fmt.Println(w)
    fmt.Println(c)
}
func w0(h int, m [][]int, w []int, c []int) {
    if len(m[h]) == 0 { // 叶节点
        return
    }
    // 有若干个直接孩子
    // 1 7个
    // 3 10个
    colors := make(map[int]int)
    // 1 20
    // 3 45
    weihts := make(map[int]int)
    for _, child := range m[h] {
        w0(child, m, w, c)
        colors[c[child]]++
        weihts[c[child]] += +w[c[child]]
    }
    for color, _ := range colors {
        w[h] = getMax(w[h], colors[color]+weihts[color])
    }
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

执行结果如下: 图片


左神java代码