二叉树的递归套路——派对的最大快乐值

派对的最大快乐值

员工信息的定义如下：

public static class Employee{public int happy;//这名员工可以带来的快乐值List<Employee> subordinates;//这名员工有哪些直接下级
}

公司的每个员工都符合Employee类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。

这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则:

1. 如果某个员工来了，那么这个员工的所有直接下级都不能来
2. 派对的整体快乐值是所有到场员工快乐值的累加
3. 你的目标是让派对的整体快乐值尽量大

给定一棵多叉树的头节点boss，请返回派对的最大快乐值。

第一种可能性：X结点来（就是给X结点发请柬），假设X有三个直接下级a,b,c，如果给X发请柬的话，快乐值就是：

X自己的快乐值
+
a不来情况下整颗子树的快乐值
+
b不来情况下整颗子树的快乐值
+
c不来情况下整颗子树的快乐值，

因为a,b,c不能来。

第二种可能性：X结点不来（就是不给X发请柬），假设X有三个直接下级a,b,c，如果不给X发请柬的话，快乐值就是：

X自己的快乐值0
+
max{a来的情况下整颗树的快乐值，a不来的情况下整棵树的快乐值}
+
max{b来的情况下整颗树的快乐值，b不来的情况下整棵树的快乐值}
+
max{c来的情况下整颗树的快乐值，c不来的情况下整棵树的快乐值}

所以任何子树都需要返回的信息就是：

• 头结点来的情况下，整颗子树的快乐值是多少
• 头结点不来的情况下，整颗子树的快乐值是多少

public static class Info{public int yes;// 对于任何子树都要返回 头结点来的情况下，整颗子树的快乐值public int no;// 对于任何子树都要返回 头结点不来的情况下，整颗子树的快乐值public Info(int y,int n) {yes=y;no=n;}}

完整代码：

package com.harrison.class08;import java.util.ArrayList;
import java.util.List;public class Code04_MaxHappy {public static class Employee{public int happy;//这名员工可以带来的快乐值List<Employee> nexts;//这名员工有哪些直接下级public Employee(int h) {happy = h;nexts = new ArrayList<>();}}public static class Info{public int yes;// 对于任何子树都要返回 头结点来的情况下，整颗子树的快乐值public int no;// 对于任何子树都要返回 头结点不来的情况下，整颗子树的快乐值public Info(int y,int n) {yes=y;no=n;}}public static Info process1(Employee x) {if(x==null) {return new Info(0, 0);}// X来的情况下先直接获得X的快乐值int yes=x.happy;// X不来情况下，快乐值就是0int no=0;// X来：累加上X的直接下级不来的情况下的快乐值// X不来：累加上X的直接下级来的情况和不来的情况 的 最大值for(Employee next:x.nexts) {Info nextInfo=process1(next);yes+=nextInfo.no;no+=Math.max(nextInfo.yes, nextInfo.no);}return new Info(yes, no);}public static int maxHappy1(Employee head) {Info allInfo=process1(head);return Math.max(allInfo.yes, allInfo.no);}// 当前来到的节点叫cur，// up表示cur的上级是否来，// 该函数含义：// 如果up为true，表示在cur上级已经确定来，的情况下，cur整棵树能够提供最大的快乐值是多少？// 如果up为false，表示在cur上级已经确定不来，的情况下，cur整棵树能够提供最大的快乐值是多少？public static int process2(Employee cur, boolean up) {if (up) { // 如果cur的上级来的话，cur没得选，只能不来int ans = 0;for (Employee next : cur.nexts) {ans += process2(next, false);}return ans;} else { // 如果cur的上级不来的话，cur可以选，可以来也可以不来int p1 = cur.happy;int p2 = 0;for (Employee next : cur.nexts) {p1 += process2(next, true);p2 += process2(next, false);}return Math.max(p1, p2);}}public static int maxHappy2(Employee boss) {if (boss == null) {return 0;}return process2(boss, false);}public static void generateNexts(Employee e,int level,int maxLevel,int maxNexts,int maxHappy) {if(level>maxLevel) {return ;}int nextSize=(int)(Math.random()*(maxNexts+1));for(int i=0; i<nextSize; i++) {Employee next=new Employee((int)(Math.random()*(maxHappy+1)));e.nexts.add(next);generateNexts(next, level+1, maxLevel, maxNexts, maxHappy);}}public static Employee generateBoss(int maxLevel,int maxNexts,int maxHappy) {if(Math.random()<0.02) {return null;}Employee boss=new Employee((int)(Math.random()*(maxHappy+1)));generateNexts(boss, 1, maxLevel, maxNexts, maxHappy);return boss;}public static void main(String[] args) {int maxLevel = 4;int maxNexts = 7;int maxHappy = 100;int testTimes = 100000;for (int i = 0; i < testTimes; i++) {Employee boss = generateBoss(maxLevel, maxNexts, maxHappy);if (maxHappy1(boss) != maxHappy2(boss)) {System.out.println("Oops!");}}System.out.println("finish!");}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！