10、算法与数据结构 - 实战：树形DP
给定一个二叉树，判断是否是平衡二叉树
如果左子树是平衡二叉树，并且右子树是平衡二叉树，并且两子树高度差不大于1，则当前子树是平衡二叉树。
二叉树递归：
1、 定义信息体；
2、 确定basecase返回的信息；
3、 左右子节点递归收集信息；
4、 根据子节点信息，计算并返回自己的信息；
/**
* 给定一个二叉树，判断是否是平衡二叉树
*/
public class TreeRecursion01 {
public static boolean isBalance(Node head) {
Info info = process(head);
return info.isBalance;
}
private static Info process(Node node) {
// 1、base case： 空树，高度为0，是平衡
if (node == null) {
Info info = new Info();
info.isBalance = true;
info.height = 0;
return info;
}
// 2、左右递归收集信息
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
// 3、根据子信息，计算自己的信息
Info info = new Info();
//如果左子树是平衡二叉树，并且右子树是平衡二叉树，并且两子树高度差不大于1，则当前子树也是平衡二叉树
if (leftInfo.isBalance && rightInfo.isBalance && Math.abs(leftInfo.height - rightInfo.height) <= 1) {
info.isBalance = true;
}
//取左右子树中高度较大的加一，作为当前子树的高度
info.height = Math.max(leftInfo.height, rightInfo.height) + 1;
return info;
}
private static class Info {
private boolean isBalance; //是否平衡
private int height; //高度
}
private static class Node {
private int value;
private Node left;
private Node right;
}
}
给定一个二叉树，返回二叉树任意节点中最大的距离
三种可能性：
- 左树的最大节点距离是整棵树的最大距离
- 右树的最大节点距离是整棵树的最大距离
- 经过头节点的最大节点距离（左树高+右树高+1），是整棵树的最大距离
所以需要信息：
- 树高
- 树的最大节点距离
/**
* 给定一个二叉树，返回二叉树任意节点中最大的距离
*/
public class TreeRecursion02 {
public static int findMaxDistance(Node head) {
Info info = process(head);
return info.maxDistance;
}
private static Info process(Node node) {
// base case：空树
if (node == null) {
Info info = new Info();
info.height = 0;
info.maxDistance = 0;
return info;
}
// 左右递归收集子节点信息
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
Info info = new Info();
//当前子树的最大距离 = 左子树的最大距离、右子树的最大距离、左子树高度+1+右子树高度，三者的最大值
info.maxDistance = Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), leftInfo.height + 1 + rightInfo.height);
//当前子树的高度 = 左子树的高度、右子树的高度，二者中的最大值+1
info.height = Math.max(leftInfo.height, rightInfo.height) + 1;
return info;
}
private static class Info {
private int height; // 树高度
private int maxDistance; // 当前树的节点最大距离
}
private static class Node {
private int value;
private Node left;
private Node right;
}
}
给定一个二叉树，返回其二叉搜索子树中最大子树的节点数
也就是整棵二叉树可能是不满足搜索二叉树结构的，但是它的子树有可能是搜索二叉树，返回它的满足搜索二叉树结构的子树中，最大的子树的节点数。
三种情况：
- 左子树中最大搜索二叉树节点数
- 右子树中最大搜索二叉树节点数
- 左右子树都是二叉搜索树，左子树的最大值 < 当前节点值 < 右子树的最小值，左右子树的节点数+1
所以需要的信息：
- 左子树最大搜索二叉树节点数
- 右子树最大搜索二叉树节点数
- 左子树最大值
- 右子树最小值
- 左子树是否搜索二叉树
- 右子树是否搜索二叉树
/**
* 给定一个二叉树，返回其二叉搜索子树中最大子树的结点数
*/
public class TreeRecursion03 {
public static int findMaxSubAllBSTSize(Node head) {
if (head == null) return 0;
Info info = process(head);
return info.maxSubAllBSTSize;
}
private static Info process(Node node) {
if (node == null) return null;
// 递归收集左右节点信息
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
boolean isAllBST; //是否是二叉搜索树
int maxSubAllBSTSize; //最大二叉搜索子树的结点数
int max; //当前子树最大值
int min; //当前子树最小值
//根据从左右子树收集回来的信息，计算当前节点的max，min
max = node.value;
min = node.value;
if (leftInfo != null) {
max = Math.max(max, leftInfo.max);
min = Math.min(min, leftInfo.min);
}
if (rightInfo != null) {
max = Math.max(max, rightInfo.max);
min = Math.min(min, rightInfo.min);
}
//预设当前子树非二叉搜索数，最大二叉搜索子树节点数位左子树和右子树中maxSubAllBSTSize的最大值
isAllBST = false;
maxSubAllBSTSize = Math.max((leftInfo == null ? 0 : leftInfo.maxSubAllBSTSize), (rightInfo == null ? 0 : rightInfo.maxSubAllBSTSize));
//判断当前子树是否是二叉搜索数，是的话，更新isAllBST，maxSubAllBSTSize
if ((leftInfo == null || leftInfo.isAllBST) //左子树是二叉搜索树
&& ((rightInfo == null || rightInfo.isAllBST)) //右子树是二叉搜索树
&& (leftInfo == null || leftInfo.max < node.value) //左子树的最大值小于当前节点的值
&& (rightInfo == null || rightInfo.min > node.value) //右子树的最小值大于当前节点的值
) {
isAllBST = true;
maxSubAllBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubAllBSTSize) + 1 + (rightInfo == null ? 0 : rightInfo.maxSubAllBSTSize);
}
// 整合当前子树信息，返回
Info info = new Info();
info.isAllBST = isAllBST;
info.maxSubAllBSTSize = maxSubAllBSTSize;
info.max = max;
info.min = min;
return info;
}
private static class Info {
private boolean isAllBST; //是否是二叉搜索树
private int maxSubAllBSTSize; //最大二叉搜索子树的结点数
private int max; //当前子树最大值
private int min; //当前子树最小值
}
private static class Node {
private int value;
private Node left;
private Node right;
}
}
开心派对问题
一个公司开派对，可以决定某个员工来或者不来。如果一个员工来，则直接下级不能来。每个员工都有自己的快乐值，0个或者若干个直接下级。求派对的最大快乐值（所有来参加派对的员工的快乐值之和）。
当前节点为头的子树的最大快乐值：
- 头节点来，则头节点的自己快乐值 + 它的所有子节点不来时的最大快乐值
- 头节点不来，在它的所有子节点的 Math.max(来的最大收益，不来的最大收益) 相加
所以需要信息：
- 当前节点来时，以它为头的子树的最大收益
- 当前节点不来时，以它为头的子树的最大收益
/**
1. 开心派对问题：
2. 一个公司开派对，可以决定某个员工来或者不来
3. 如果一个员工来，则直接下级不能来
4.
5. 每个员工都有自己的快乐值，0个或者若干个直接下级
6.
7. 求派对的最大快乐值（所有来参加派对的员工的快乐值之和）
*/
public class TreeRecursion04 {
public static int findMaxHappy(Employee boss) {
Info info = process(boss);
return Math.max(info.maxHappy1, info.maxHappy2);
}
private static Info process(Employee employee) {
// base case：没有子节点，来时最大快乐值是自己的开了值，不来时的最大快乐值则是0
if (employee.nexts.isEmpty()) {
Info info = new Info();
info.maxHappy1 = employee.happy;
info.maxHappy2 = 0;
return info;
}
int maxHappy1 = 0; //该员工来时，子树的最大快乐值
int maxHappy2 = 0; //该员工不来，子树的最大快乐值
for (Employee next : employee.nexts) {
Info nextInfo = process(next); // 收集所有子节点信息
maxHappy1 += nextInfo.maxHappy2; //当前员工来，直接下级不能来，当前员工的快乐值+直接下级不来时最大快乐值
maxHappy2 += Math.max(nextInfo.maxHappy1, nextInfo.maxHappy2); //当前员工不来，则取直接下级来时和不来的最大快乐值中的最大值
}
// 整合当前节点信息返回
Info info = new Info();
info.maxHappy1 = maxHappy1;
info.maxHappy2 = maxHappy2;
return info;
}
private static class Info {
private int maxHappy1; //该员工来时，子树的最大快乐值
private int maxHappy2; //该员工不来，子树的最大快乐值
}
private static class Employee {
private int happy;
private List<Employee> nexts;
}
}
给定一颗二叉树，判断其是否是满二叉树
解法：
1、 定义信息体，包含树高和数节点数两个信息；
2、 递归收集二叉树的信息，得到根节点信息；
3、 用根节点信息进行计算，((1<<info.height)+1)==info.size为true，则时满二叉树；
/**
* 给定一颗二叉树，判断其是否是满二叉树
*/
public class TreeRecursion05 {
public static boolean isFull(Node head) {
Info info = process(head);
return ((1 << info.height) + 1) == info.size;
}
private static Info process(Node node) {
if (node == null) {
Info info = new Info();
info.size = 0;
info.height = 0;
return info;
}
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
Info info = new Info();
info.size = leftInfo.size + 1 + rightInfo.size;
info.height = Math.max(leftInfo.height, rightInfo.height) + 1;
return info;
}
private static class Info {
private int height;
private int size;
}
private static class Node {
private int value;
private Node left;
private Node right;
}
}
给定一个二叉树，返回其二叉搜索子树中最大子树的头结点
与“求最大二叉搜索子树中的节点数”的解法类似
/**
* 给定一个二叉树，返回其二叉搜索子树中最大子树的头结点
*/
public class TreeRecursion06 {
public static Node findMaxSubBSTHead(Node head) {
Info info = process(head);
return info == null ? null : info.maxSubBSTHead;
}
private static Info process(Node node) {
if (node == null) return null;
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
//预设当前子树不是二叉搜索树，从左右子树返回的信息中，计算max、min、maxSubBSTSize、maxSubBSTHead
Info info = new Info();
info.max = node.value;
info.min = node.value;
info.maxSubBSTSize = 0;
if (leftInfo != null) {
info.max = Math.max(leftInfo.max, info.max);
info.min = Math.min(leftInfo.min, info.min);
info.maxSubBSTSize = leftInfo.maxSubBSTSize;
info.maxSubBSTHead = leftInfo.maxSubBSTHead;
}
if (rightInfo != null) {
info.max = Math.max(rightInfo.max, info.max);
info.min = Math.min(rightInfo.min, info.min);
if (rightInfo.maxSubBSTSize > info.maxSubBSTSize) {
info.maxSubBSTHead = rightInfo.maxSubBSTHead;
info.maxSubBSTSize = rightInfo.maxSubBSTSize;
}
}
//判断当前子树是否是二叉搜索树，若是则maxSubBSTHead设置为当前结点，重新计算maxSubBSTSize
if ((leftInfo == null || leftInfo.maxSubBSTHead == node.left)
&& (rightInfo == null || rightInfo.maxSubBSTHead == node.right)
&& (leftInfo == null || leftInfo.max < node.value)
&& (rightInfo == null || rightInfo.min > node.value)) {
info.maxSubBSTHead = node;
info.maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize) + 1 + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize);
}
return info;
}
private static class Info {
private Node maxSubBSTHead; //最大二叉搜索子树头结点
private int maxSubBSTSize; //最大二叉搜索子树大小
private int max; //子树最大值
private int min; //子树最小值
}
private static class Node {
private int value;
private Node left;
private Node right;
}
}
给定一颗二叉树，判断其是否是完全二叉树
四种情况：
- 整棵树是满二叉树
- 左子树是完全二叉树，右子树是满二叉树，左子树比右子树高度高1
- 左子树是满二叉树，右子树是满二叉树，左子树比右子树高度高1
- 左子树是满二叉树，右子树是完全二叉树，左右子树高度相同
所以需要信息：
- 以当前节点为头的树是否是满二叉树
- 以当前节点为头的树是否是完全二叉树
- 以当前节点为头的树的树高
/**
* 给定一颗二叉树，判断其是否是完全二叉树
*
* 四种情况：
* 1.整棵树是满二叉树
* 2.左子树是完全二叉树，右子树是满二叉树，左子树比右子树高度高1
* 3.左子树是满二叉树，右子树是满二叉树，左子树比右子树高度高1
* 4.左子树是满二叉树，右子树是完全二叉树，左右子树高度相同
*/
public class TreeRecursion07 {
public static boolean isCBT(Node head) {
Info info = process(head);
return info.isCBT;
}
private static Info process(Node node) {
// base caes：空树，是满二叉树，是完全二叉树，树高0
if (node == null) {
Info info = new Info();
info.isCBT = true;
info.isFull = true;
info.height = 0;
return info;
}
// 从左右子树收集信息
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
// 根据从左右子树收集回来的信息，计算height和isFull
Info info = new Info();
info.height = Math.max(leftInfo.height, rightInfo.height) + 1;
info.isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
// 根据从左右子树收集回来的信息，计算isCBT
if (info.isFull) {
info.isCBT = true; //满足条件1
} else {
if (leftInfo.isCBT && rightInfo.isCBT) {
if ((leftInfo.isCBT && rightInfo.isFull && leftInfo.height - rightInfo.height == 1) //满足条件2
|| (leftInfo.isFull && rightInfo.isFull && leftInfo.height - rightInfo.height == 1) //满足条件3
|| (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height)) {
//满足条件4
info.isCBT = true;
}
}
}
return info;
}
private static class Info {
private boolean isFull; //当前子树是否是满二叉树
private boolean isCBT; //当前子树是否是完全二叉树
private int height; //当前子树高度
}
private static class Node {
private int value;
private Node left;
private Node right;
}
}
二叉树中寻找两个结点的最低公共祖先
普通方法：
1、 遍历一遍二叉树，用一个map记录子节点和父节点的映射关系；
2、 先挑其中一个节点，沿着map往上找，找到的节点记录到set中；
3、 再拿另一个节点，沿着map往上找，找到在set中存在的节点，返回这个结点；
树形DP解法：
假设要求a节点和b节点的最低公共祖先，从左右子树收集信息，是否发现a节点，是否发现b节点，如果都发现了，记录当前节点是答案节点。
树形DP解法需要收集的信息：
- 子树答案节点
- 是否发现a节点
- 是否发现b节点
/**
* 二叉树中寻找两个结点的最低公共祖先
*/
public class TreeRecursion08 {
public static Node findLowestAncestor(Node head, Node node1, Node node2) {
Info info = process(head, node1, node2);
return info == null ? null : info.result;
}
private static Info process(Node node, Node node1, Node node2) {
if (node == null) return null;
//分别往左右子树收集信息
Info leftInfo = process(node, node1, node2);
Info rightInfo = process(node, node1, node2);
//根据左右子树的信息，计算findNode1和findNode2
boolean findNode1 = node == node1 || leftInfo.findNode1 || rightInfo.findNode1;
boolean findNode2 = node == node2 || leftInfo.findNode2 || rightInfo.findNode2;
//如果左子树或右子树返回的信息中已经记录了最低公共祖先，则记录到当前节点的信息中，往上返回
Node result = null;
if (leftInfo.result != null) result = leftInfo.result;
if (rightInfo.result != null) result = rightInfo.result;
//到这里result依然为空，则根据findNode1和findNode2的值进行计算，如果都为true，代表当前这个结点就是最低公共祖先
if (result == null) {
if (findNode1 && findNode2) result = node;
}
Info info = new Info();
info.result = result;
info.findNode1 = findNode1;
info.findNode2 = findNode2;
return info;
}
private static class Info {
private Node result; //node1和node2的最低公共祖先
private boolean findNode1; //是否已经找到了node1
private boolean findNode2; //是否已经找到了node2
}
private static class Node {
private int value;
private Node left;
private Node right;
}
}