二叉树递归套路（4）（最低公共祖先、派对的最大快乐值）二叉树递归套路（4）：最低公

今天继续二叉树的递归套路。
一、最低公共祖先给定一个二叉树的头节点，和另外两个节点a、b，返回a、b的最低公共祖先。
最低公共祖先定义：a、b往上找，第一个相同的祖先（这个公共祖先也可能是a或b自己）
1、递归套路思路对于二叉树中的任意一个节点X，以及两个节点a、b，a和b的最低公共祖先分为两种情况。
（1）与X无关，即最低公共祖先不是X
a、b在左树中某个点汇聚了
a、b在右树中某个点汇聚了
a、b在左树和右树中不全
（2）与X有关，即最低公共祖先是X
左树中找到a、b中的一个，右树找到另一个
X是a，在左树或右树中找到b
X是b，在左树或右树中找到a
也就是每次从左树和右树中我们都需要是否有a，是否有b，a和b汇聚的最低祖先。所以，可以定义如下的Info类

/** * @author Java和算法学习：周一 */ public static class Info{ public boolean findA; public boolean findB; public Node answer; public Info(boolean findA, boolean findB, Node answer) { this.findA = findA; this.findB = findB; this.answer = answer; } }

2、递归套路代码（1）首先判断为空时好不好设置，此时是好设置的，节点为空时new Info(false, false, null)，即认为空节点不含有a、不含有b、最低公共祖先为null。
（2）然后根据列出的所有可能性，编写递归套路的代码，因为要整个形成递归，所以每一步都要返回Info类。（无脑拿到左右子树的Info、拼凑自己的Info、返回自己的Info）

/** * @author Java和算法学习：周一 */ public static Info process(Node x, Node a, Node b) { if (x == null) { return new Info(false, false, null); }// 获取左右子树的信息 Info leftInfo = process(x.left, a, b); Info rightInfo = process(x.right, a, b); // 拼凑自己的信息 // 不要忽略了自己是a或b的情况 boolean findA = leftInfo.findA || rightInfo.findA || x == a; boolean findB = leftInfo.findB || rightInfo.findB || x == b; Node answer = null; if (leftInfo.answer != null) { // 左树中有答案，则此答案就是最终的答案 answer = leftInfo.answer; } else if (rightInfo.answer != null) { // 右树中有答案，则此答案就是最终的答案 answer = rightInfo.answer; } else { // 左树和右树都没有答案，但是找到了a和b，则答案就是当前节点X if (findA && findB) { answer = x; } }return new Info(findA, findB, answer); }

（3）主函数调用递归方法获取结果

/** * @author Java和算法学习：周一 */ public static Node lowestAncestor(Node head, Node a, Node b) { if (head == null) { return null; } return process(head, a, b).answer; }

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/LowestAncestor.java
二、派对的最大快乐值员工的信息定义如下：

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

一个员工只有一个直接上级。也就是这个公司员工的层级结构就是一个多叉树。
现在公司邀请员工参加派对，要求不能同时邀请员工和员工的任一下级（即直接上下级不能同时邀请），如何邀请员工，才能使得参加派对的员工的快乐值是所有情况中最大的。最后返回最大的快乐值。
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) )
最后，最大的快乐值为以上两种情况的最大值。
也就是每次从左树和右树中我们都需要来，不来的最大快乐值，所以，可以定义如下的Info类

/** * @author Java和算法学习：周一 */ public static class Info { // 来的最大收益 public int yes; // 不来的最大收益 public int no; public Info(int yes, int no) { this.yes = yes; this.no = no; } }

2、递归套路代码（1）首先判断为空时好不好设置，此时是好设置的，节点为空时new Info(0, 0)，即认为空节点表示来的最大收益为0、不来的最大收益为0。
（2）然后根据列出的所有可能性，编写递归套路的代码，因为要整个形成递归，所以每一步都要返回Info类。（无脑拿到所有子树的Info、拼凑自己的Info、返回自己的Info）

/** * @author Java和算法学习：周一 */ public static Info process(Employee x) { if (x == null) { return new Info(0, 0); }// x不来的最大快乐值 int no = 0; // x来的最大快乐值 int yes = x.happy; for (Employee e : x.next) { Info nextInfo = process(e); // x来，则所有下级都不能来 yes += nextInfo.no; // x不来，则求每个下级来或不来的最大值 no += Math.max(nextInfo.yes, nextInfo.no); }return new Info(yes, no); }

（3）主函数调用递归方法获取结果

/** * @author Java和算法学习：周一 */ public static int maxHappy(Employee head) { if (head == null) { return 0; } Info processInfo = process(head); return Math.max(processInfo.yes, processInfo.no); }

【二叉树递归套路（4）（最低公共祖先、派对的最大快乐值）】所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/MaxHappy.java