明天持续二叉树的递归套路。
一、最低公共先人
给定一个二叉树的头节点，和另外两个节点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<Employee> 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);}所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/MaxHappy.java