树形dp
概述
- 使用前提：如果题目求解的目标是S规则，则求解的流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中
- 套路步骤：
（1）以某一个节点X为头节点的子树中，分析答案有哪些可能性（难点），并且这种分析是以X的左子树，X的右子树和X的整个树的角度来考虑可能性的
（2）根据（1）的可能性分析，列出所有需要的信息
（3）合并（2）的信息，对左右树提出同样的要求，并写出信息结构
（4）设计递归函数，递归函数是处理以X为头节点的情况下的答案，包括设计递归的basecase，默认直接得到左右树的所有信息（黑盒的构造），以及把可能性做整合，并且要返回第三步的信息结构（黑盒的拆解）（在以下题目中，递归函数设计部分对黑盒的使用用更为详细的说明）
题目一：二叉树节点间的最大距离问题
如图：a到b的距离为2，d到c的距离为4，d到k的距离为6
- 枚举（暴力）思路：任意两个节点直接均可以求出直接的距离，所有可以求出任意两节点距离后找最大值，但是时间复杂度过高
- 树形dp思路：
1 可能性分析：两大类，X是否参与最大值
（1）X参与，X左树的最低端到X右树的最低端，左树的高度 + 1 + 右树的高度
（2）X不参与，左右树内部解决，左树的最大距离，右树的最大距离
（3）X的最大长度就在：左树的最大距离；右树的最大距离；左树的高度 + 1 + 右树的高度，三者中的最大值
2 信息要求
（1）情况一：左树的高度，右树的高度
（2）情况二：左树的最大距离，右树的最大距离
（3）综上所述：子树需要给父节点返回的信息结构：最大距离，高度
3 递归函数设计
（1）basecase：节点为空时返回信息（0，0）
（2）黑盒的构造：假设直接得到了左右子树想要的信息结构
（3）拆解黑盒：给出具体一个节点在得到左右子树信息后，如何整合出该节点的信息结构
public static class Node{ //树结点 public int value; public Node left; public Node right; public Node(int date){ //初始化 this.value = date; } } public static class Info{ //信息返回类型 public int maxDistance; public int height; public Info(int maxDistance, int height){ this.maxDistance = maxDistance; this.height = height; } } public static int maxDistance(Node head){ //最大距离函数 return process(head).maxDistance; } public static Info process(Node x){ //求以X为头的整棵树的Info信息 if (x == null){ //basecase return new Info(0, 0); } //黑盒的构造：递归调用得到左右子树的Info信息 Info leftInfo = process(x.left); Info rightInfo = process(x.right); //信息的整合 //不含X时左右树提供的最大距离 int leftDistance = leftInfo.maxDistance; int rightDistance = rightInfo.maxDistance; //含X时的最大距离 int xDistance = leftInfo.height + 1 + rightInfo.height; //拆解黑盒：给出该节点信息的解决方法 int maxDistance = Math.max(xDistance, Math.max(leftDistance, rightDistance)); int height = Math.max(leftInfo.height, rightInfo.height) + 1; return new Info(maxDistance, height); }
题目二：排队最大快乐值（多叉树问题）
- 树形dp思路：
1 可能性分析：两大类，X是否参与最大值
（1）X参与，最大值：X的值 + X子树的顶点不参与的情况下，提供的最大值
（2）X不参与，最大值：0 + max（子树顶点参与，子树顶点不参与）
（3）最大值：X参与，X不参与的最大值
2 信息要求
（1）情况一：头节点参与的最大值
（2）情况二：头节点不参与的最大值
（3）综上所述：子树需要给父节点返回的信息结构：（子树顶点参与，子树顶点不参与）
3 递归函数设计
（1）basecase：节点为叶子节点时，返回（该节点的值，0）
（2）黑盒的构造：假设直接得到了所有子树想要的信息结构
（3）拆解黑盒：给出具体一个节点在得到所有子树信息后，如何整合出该节点的信息结构
public static class Employee{ //员工信息类 public int happy; //快乐值要求达到最大 public List<Employee> nexts; //子节点 public Employee(int date){ //初始化 this.happy = date; } } public static class Info{ //信息返回类型 public int xMaxHappy; //x节点参与 public int maxHappy; //x不参与 public Info(int xMaxHappy, int maxHappy){ this.xMaxHappy = xMaxHappy; this.maxHappy = maxHappy; } } public static int maxHappy(Employee boss){ //最大快乐值 Info headInfo = process(boss); return Math.min(headInfo.xMaxHappy, headInfo.maxHappy); } public static Info process(Employee x){ //返回x的Info信息 if (x.nexts.isEmpty()){ //basecase return new Info(x.happy, 0); } int xMaxHappy = x.happy; int maxHappy = 0; for (Employee next : x.nexts){ //遍历x的子树 //黑盒的构造 Info nextInfo = process(next); //拆黑盒 xMaxHappy += nextInfo.maxHappy; maxHappy += Math.max(nextInfo.xMaxHappy, nextInfo.maxHappy); } return new Info(xMaxHappy, maxHappy); }
题目三：判断是否为满二叉树
- 树形dp思路：
1 可能性分析：深度H，节点数为N
（1）是满二叉树：N == 2 ^ H - 1
（2）不是满二叉树：N != 2 ^H - 1
2 信息要求
（1）父节点的H = 左右子树中H的较大值 + 1
（2）父节点的N = 左N + 右N
（3）子树需要给父节点返回的信息结构：深度，节点树
3 递归函数设计
（1）basecase：节点为空，返回（0，0）
（2）黑盒的构造：假设直接得到了左右子树想要的信息结构
（3）拆解黑盒：给出具体一个节点在得到所有子树信息后，如何整合出该节点的信息结构
public static class Node{ int value; Node left; Node right; public Node(int date){ this.value = date; } } public static class Info{ public int height; //树的高度 public int num; //节点数 public Info(int height, int num){ //初始化 this.height = height; this.num = num; } } public static boolean isFull(Node head){ //判断是否为满二叉树 Info headInfo = process(head); //1 << x, 2的x次方 return headInfo.num == (1 << headInfo.height - 1); } public static Info process(Node x){ //返回x的Info信息 if (x == null){ //basecase return new Info(0, 0); } //黑盒子的构建 Info left = process(x.left); Info right= process(x.right); //拆解黑盒 int height = Math.max(left.height, right.height) + 1; int num = left.num + right.num + 1; return new Info(height, num); }
题目四：判断是否为平衡二叉树
- 树形dp思路：
1 可能性分析：
（1）X平衡：左右均为平衡二叉树，且|左高度 - 右高度| <= 1
（2）X不平衡，不满足平衡的一条就行
2 信息要求
（1）左右子树是否平衡
（2）左右树的高度
（3）子树需要给父节点返回的信息结构：是否平衡，高度
3 递归函数设计
（1）basecase：节点为空，返回（true，0）
（2）黑盒的构造：假设直接得到了左右子树想要的信息结构
（3）拆解黑盒：给出具体一个节点在得到所有子树信息后，如何整合出该节点的信息结构
public static class Node{ int value; Node left; Node right; public Node(int date){ this.value = date; } } public static class Info { //Info public boolean isBalanced; //树是否平衡 public int height; public Info(boolean isBalanced, int height){ //构造函数 this.isBalanced = isBalanced; this.height = height; } } public static boolean isBalancedTree(Node head){ return process(head).isBalanced; } public static Info process(Node x){ //返回x的Info信息 if (x == null){ //basecase return new Info(true, 0); } //黑盒构造 Info leftTree = process(x.left); Info rightTree= process(x.right); //拆解黑盒 int height = Math.max(leftTree.height, rightTree.height) + 1; boolean isBalanced = leftTree.isBalanced && rightTree.isBalanced && Math.abs(leftTree.height - rightTree.height) < 2; return new Info(isBalanced, height); }
题目五：判断是否为二叉排序树
- 树形dp思路：
1 可能性分析：
（1）X是：左max < head.value < 右min，左右均为二叉排序树
（2）X不是，不满足条件
2 信息要求
（1）左右子树是否为二叉排序树
（2）左的max，min；右的min，max
（1）子树需要给父节点返回的信息结构：是否为二叉排序树，左右的max，min
3 递归函数设计
（1）basecase：节点为空，因为max，min不好设置，直接返回null
（2）黑盒的构造：假设直接得到了左右子树想要的信息结构
（3）拆解黑盒：给出具体一个节点在得到所有子树信息后，如何整合出该节点的信息结构
public static class Node{ int value; Node left; Node right; public Node(int date){ this.value = date; } } public static class Info { //info public boolean isBST; //树是否为搜索树 public int min; //树的最小值 public int max; //树的最大值 public Info(boolean isBST, int min, int max){ //构造函数 this.isBST = isBST; this.min = min; this.max = max; } } public static boolean isBSTree(Node head){ return process(head).isBST; } public static Info process(Node x){ //返回x的Info if (x == null){ //空树的min,max不好设置，直接设置为null return null; } //黑盒构造 Info leftTree = process(x.left); //递归调用 Info rightTree= process(x.right); //拆解黑盒 int min = x.value; //min，max的设置 int max = x.value; if (leftTree != null){ //左子树为空 min = Math.min(min, leftTree.min); max = Math.max(max, leftTree.max); } if (rightTree != null){ //右子树为空 min = Math.min(min, rightTree.min); max = Math.max(max, rightTree.max); } boolean isBST = true; //isBST设置 if (leftTree != null && (leftTree.isBST || leftTree.max > x.value)){ //左不为空的条件下：左子树不是搜索二叉树或左的max > head,value //不满足搜索二叉树 isBST = false; } if (rightTree != null && (rightTree.isBST || rightTree.min < x.value)){ isBST = false; } return new Info(isBST, min, max); }
