树形dp套路
https://www.cnblogs.com/mhpp/p/6628548.html
树形dp套路 树形dp套路使用前提： 如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中
1. 树形dp套路
【站在 左树也能要信息，右树也能要信息，考虑当前头，的角度】
树形dp套路第一步：
以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的
树形dp套路第二步：
根据第一步的可能性分析，列出所有需要的信息
树形dp套路第三步：
合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构
树形dp套路第四步：
设计递归函数，递归函数是处理以X为头节点的情况下的答案。
包括设计递归的basecase，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构这四个小步骤
题目一 ：二叉树节点间的最大距离问题
从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫作a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离。
1. 以X的左子树、X的右子树和X整棵树的角度来考虑可能性的
1) 和x有关，那就是左子树上最长的 到x 然后 到右子树
2) 和x无关
A. 只与x的左子树有关 [ 如下图 ]
B. 只与x的右子树有关
2. 根据第一步的可能性分析，列出所有需要的信息
左远到右远
左树上的最大距离，左远对应的左树的高度。
右树上的最大距离，右远对应的右树的高度。
3.合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构【求并集】
如左树要最小，右树要最大，那么信息结构就是两者都要求。
4.设计递归函数，递归函数是处理以X为头节点的情况下的答案。
包括设计递归的basecase，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构这四个小步骤
public class Code02_MaxDistanceInTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 主函数，得到最大距离，输入一个头结点
public static int maxDistance(Node head) {
return process(head).maxDistance;
}
public static class Info{
public int maxDistance;
public int height;
public Info(int dis, int h) {
maxDistance = dis;
height = h;
}
}
public static Info process(Node x) {//通过proess函数得到info
// 1. basecase
if(x == null) {
return new Info(0,0);//构造新的info返回
}
// 2. 默认直接得到左树和右树的所有信息
Info leftInfo = process(x.left);// 用了黑盒
Info rightInfo = process(x.right);
// info 拆解黑盒，拆出该函数的意义 ，这里是得到info【maxDistance，height】
// 3. 可能性做整合 拆解黑盒
int p1 = leftInfo.maxDistance;//情况一
int p2 = rightInfo.maxDistance;//情况二
int p3 = leftInfo.height + 1 + rightInfo.height;//情况三
int maxDistance = Math.max(p3, Math.max(p1, p2));
int height = Math.max(leftInfo.height, rightInfo.height) + 1 ;
// 4. 返回第三步的信息结构
return new Info(maxDistance, height);
}
}
题目二 派对的最大快乐值
员工信息的定义如下:
class Employee {
public int happy; // 这名员工可以带来的快乐值
List<Employee> subordinates; // 这名员工有哪些直接下级 }
公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。 这个公司现在要办party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下规则。
1.如果某个员工来了，那么这个员工的所有直接下级都不能来
2.派对的整体快乐值是所有到场员工快乐值的累加
3.你的目标是让派对的整体快乐值尽量大
给定一棵多叉树的头节点boss，请返回派对的最大快乐值。
首先从X开始分析，x整棵树可能性
public static class Employee {
public int happy; // 这名员工可以带来的快乐值
public List<Employee> nexts; // 这名员工有哪些直接下级
}
public static int maxHappy(Employee boss) {
Info headInfo = process(boss);
return Math.max(headInfo.laiMaxHappy, headInfo.buMaxHappy);
}
// 得到一个员工，来or不来，分别对应的最大happy！！！！
public static class Info{
public int laiMaxHappy;
public int buMaxHappy;
public Info(int lai, int bu) {
laiMaxHappy = lai;
buMaxHappy = bu;
}
}
// 得到一个员工，来or不来，分别对应的最大happy！！！！
public static Info process(Employee x) {
//1. basecase
if(x.nexts.isEmpty()) {
return new Info(x.happy,0);
}
int lai = x.happy;
int bu = 0;
for(Employee next : x.nexts) {
Info nextInfo = process(next);// 2. 默得到子树的info信息
// 3. 整合信息【拆解黑盒，得到info中具体的】
lai += nextInfo.buMaxHappy;
bu += Math.max(nextInfo.laiMaxHappy, nextInfo.buMaxHappy);
}// 4. 返回info
return new Info(lai,bu);
}
题目三 最大搜索二叉子树
package class05;
public class MaxBSTSize {
public static class Node {
public int value;
Node left;
Node right;
}
public static class Info {
public int maxBSTSize;
public boolean isBST;
public int min;
public int max;
public Info(int maxBST, boolean is, int mi, int ma) {
maxBSTSize = maxBST;
isBST = is;
min = mi;
max = ma;
}
}
public static Info process(Node x){
if(x == null) {
// 不想子树感染上级，最小值给系统最大，
return new Info(0,true,Integer.MAX_VALUE,Integer.MIN_VALUE);
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
boolean isBST = false;
int maxBSTSize = leftInfo.maxBSTSize;
maxBSTSize = Math.max(maxBSTSize,rightInfo.maxBSTSize);
if(leftInfo.isBST
&& rightInfo.isBST
&& leftInfo.max < x.value
&& rightInfo.min > x.value) {
maxBSTSize = leftInfo.maxBSTSize + 1 + rightInfo.maxBSTSize;
isBST = true;
}
int min = Math.min(x.value, Math.min(leftInfo.min, rightInfo.min));
int max = Math.max(x.value, Math.max(leftInfo.max, rightInfo.max));
return new Info(maxBSTSize,isBST,min,max);
}
}