2021-11-28：有一棵树，给定头节点h，和结构数组m，下标

原创

福大大架构师每日一题

发布于 2021-11-28 23:14:32

1750

发布于 2021-11-28 23:14:32

文章被收录于专栏：福大大架构师每日一题

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数组里，比如ci = 4, 表示节点i的颜色为4，

一开始只有叶节点是有权值的，记录在w数组里，

比如，如果一开始就有wi = 3, 表示节点i是叶节点、且权值是3。

现在规定非叶节点i的权值计算方式：

根据i的所有直接孩子来计算，假设i的所有直接孩子，颜色只有a,b,k。

wi = Max {

         (颜色为a的所有孩子个数 + 颜色为a的孩子权值之和),

         (颜色为b的所有孩子个数 + 颜色为b的孩子权值之和),

         (颜色为k的所有孩子个数 + 颜色k的孩子权值之和)

请计算所有孩子的权值并返回。

来自美团。

答案2021-11-28：

这道题考的是语文。后序遍历。

当前来到h节点，

h的直接孩子，在哪呢？mh = {a,b,c,d,e}，

每个节点的颜色在哪？比如i号节点，ci就是i号节点的颜色，

每个节点的权值在哪？比如i号节点，wi就是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
    }
}

执行结果如下：