共计 3592 个字符，预计需要花费 9 分钟才能阅读完成。
明天持续二叉树的递归套路。
一、最低公共先人
给定一个二叉树的头节点，和另外两个节点 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