今天繼續二叉樹的遞歸套路。
一、最低公共祖先
給定一個二叉樹的頭節點，和另外兩個節點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
