题解 | #二叉树的镜像#字节一面面试题

派对的最大快乐值

http://www.nowcoder.com/practice/a5f542742fe24181b28f7d5b82e2e49a

员工的信息定义如下：

class TreeNode{
    public:
    int happy;                         //这名员工可以带来的快乐值
    vector<TreeNode*> next;        //这名员工有哪些直接下级
    TreeNode(int h):happy(h){}        //初始化
};

1、递归套路思路

对于任意一个以X为头，含有a、b、c三个子节点的多叉树，最大快乐值分为两种：

（1）X来参加派对

最大快乐值 = X.happy

+ a不来的max(happy)

+ b不来的max(happy)

+ c不来的max(happy)

（2）X不来参加派对

最大快乐值 = max( a来的max(happy), a不来的max(happy) )

+ max( b来的max(happy), b不来的max(happy) )

+ max( c来的max(happy), c不来的max(happy) )

最后，最大的快乐值为以上两种情况的最大值。

可定义如下：

class Max{
    public:
    int no;           //不来的最大收益
    int yes;          //来的最大收益
    Max(int n,int y):no(n),yes(y){}     //初始化
};

2、递归套路代码

Max getMax(TreeNode* root){
    if(root->next.empty()) return Max(0,root->happy);      //判断到根节点返回（不来，来）两种情况
    int n=0；                                               //root不来的最大快乐值     
    int y=root->happy;                                      //root来的最大快乐值
    for(auto r:root->next){                                 //遍历每一个直接孩子
        auto k=getMax(r);                               //获取以子孩子位根的子树的快乐情况
        y+=k.no;                                         //root来，那么所有孩子都不能来
        n+=max(k.yes,k.no);                              //root不来，所有孩子  来与不来  两种情况选择最大值
    }
    return Max(n,y);
}

3、完整代码

#include<bits/stdc++.h>
using namespace std;

class TreeNode{
    public:
    int happy;
    vector<TreeNode*> next;
    TreeNode(int h):happy(h){}
};

class Max{
    public:
    int no;
    int yes;
    Max(int n,int y):no(n),yes(y){}
};

Max getMax(TreeNode* root){
    if(root->next.empty()) return Max(0,root->happy);
    int n=0,y=root->happy;
    for(auto r:root->next){
        auto k=getMax(r);
        y+=k.no;
        n+=max(k.yes,k.no);
    }
    return Max(n,y);
}

int main(){
    int n,root;
    cin>>n>>root;
    vector<TreeNode*> happy(n);
    int t,u,v;
    for(int i=0;i<n;++i){
        cin>>t;
        happy[i]=new TreeNode(t);
    }
    for(int i=1;i<n;++i){
        cin>>u>>v;
        happy[u-1]->next.push_back(happy[v-1]);
    }
    auto x=getMax(happy[root-1]);
    cout<< max(x.no,x.yes) <<endl;
    return 0;
}