3.6 树的递归应用

在一个公司结构中

1. 每个人都有一个快乐值，最小为 0， 最大为 100
2. 每个人都只有一个领导，最高层没有领导
3. 现在要举办一个聚会，上级到，下级就不能来
   求出聚会的最大快乐值

class TreeNode {// 下级员工public List<TreeNode> children;// 快乐值public int value;public TreeNode(Integer value) {this.value = value;this.children = new ArrayList<>();}
}// 暴力递归public int maxHappyCompare(TreeNode treeNode) {int m1 = maxHappyCompare(treeNode, true);int m2 = maxHappyCompare(treeNode, false);return Math.max(m1, m2);}public int maxHappyCompare(TreeNode treeNode, boolean include) {if (treeNode == null) {return 0;}int max = 0;if (include) {for (TreeNode employee : treeNode.children) {max = Math.max(max, maxHappyCompare(employee, false));}max += treeNode.value;} else {for (TreeNode node : treeNode.children) {max = Math.max(max, maxHappyCompare(node, true));max = Math.max(max, maxHappyCompare(node, false));}}return max;}class Info8 {public int yes;public int no;public Info8(int yes, int no) {this.yes = yes;this.no = no;}}// 向子树要信息public int maxHappy(TreeNode node) {Info8 info = processMaxHappy(node);return Math.max(info.yes, info.no);}private Info8 processMaxHappy(TreeNode node) {if (node == null) {return new Info8(0, 0);}int yes = 0, no = 0;for (TreeNode child : node.children) {Info8 i1 = processMaxHappy(child);yes = Math.max(yes, i1.no);no = Math.max(no, Math.max(i1.yes, i1.no));}return new Info8(yes + node.value, no);}@Testpublic void test2() {for (int i = 0; i < 10000; i++) {TreeNode node = Reduce.treeNode(10, 0, 100);int r1 = maxHappy(node);int r2 = maxHappyCompare(node);if (r1 != r2) {System.out.println(node);r1 = maxHappy(node);r2 = maxHappyCompare(node);return;}}}

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