左神算法笔记——树形DP问题
2020-04-12 本文已影响0人
yaco
——总结左神进阶班第四、五课有关树的一些问题汇总
目录：
- 判断一颗树是否是平衡二叉树
- 寻找最大二叉搜索树（节点个数和头节点）
- 寻找一个树中最大值和最小值（节点和值）
- 求一颗二叉树上面的最远距离
- 员工活跃度问题
判断一颗树是否是平衡二叉树
基本思路：
-
首先获取所需信息：
- 当前树的左子树是否是平衡二叉树
- 当前树的右子树是否是平衡二叉树
- 当前树的左子树的高度
- 当前树的右子树的高度
-
整合所用信息
- 如果左右子树有一个不是平衡二叉树，那么当前的树肯定也不是平衡二叉树。
- 如果左右子树都是平衡二叉树，且左右子树的高度差不超过1，那么是平衡树，否则不是平衡二叉树。
代码如下：
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 创建对象信息集
static class State{
boolean isAvl; // 当前树是否是平衡二叉树
int h; // 当前树的高度
// 构造器
public State(boolean isAvl, int h) {
this.isAvl = isAvl;
this.h = h;
}
}
// 判断一颗树是否是平衡二叉树
public static boolean isAvl(TreeNode root){
return getAns(root).isAvl;
}
private static State getAns(TreeNode root) {
if(root == null) return new State(true,0);
// 获取左右子树的各自信息
State l = getAns(root.left);
State r = getAns(root.right);
// case——true;
if(!l.isAvl || !r.isAvl || Math.abs(l.h - r.h) > 1){
return new State(false,0);
}
// case——false
return new State(true,Math.max(l.h,r.h) + 1);
}
寻找最大二叉搜索树（节点个数和头节点）
LintCode910 | 寻找最大二叉搜索子树 —— 需要会员
题目描述：
给定一颗二叉树的头节点head，请返回最大搜索二叉子树的大小。
基本思路：
- 首先搜索所用信息：
- 左、右子树中最大搜索二叉树的头节点。
- 左、右子树中最大二叉搜索子树的节点个数。
- 左、右子树中的最小节点值
- 左、右子树中的最大节点值
- 进行所用信息的整合
- case1 : 如果当前左右两颗树可以整合为一颗二叉搜索树。
- case2 : 如果当前左右子树无法整为一颗二叉搜索树，从左右子树中挑选一颗较大搜索二叉树。
代码如下：
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 创建对象信息集
static class State{
TreeNode head;
int size;
int min;
int max;
public State(TreeNode head, int size, int min, int max) {
this.head = head;
this.size = size;
this.min = min;
this.max = max;
}
}
// 返回最大的二叉搜索子树的头节点
public static TreeNode getMaxBST(TreeNode root){
return getAns(root).head;
}
private static State getAns(TreeNode root) {
if(root == null) return new State(null,0,Integer.MAX_VALUE,Integer.MIN_VALUE);
// 获取左右子树的信息
State l = getAns(root.left);
State r = getAns(root.right);
// case1: 左右子树可以整合成一颗二叉搜索树
int union = 0;
if(l.head == root.left && r.head == root.right && root.val > l.max && root.val < r .min){
union = l.size + r.size + 1;
}
// case2、3
int p1 = l.size;
int p2 = r.size;
int maxSize = Math.max(Math.max(p1,p2),union);
TreeNode maxHead = p1 > p2 ? l.head : r.head;
if(maxSize == union){
maxHead = root;
}
return new State(maxHead,maxSize,
Math.min(Math.min(l.min,r.min),root.val),Math.max(Math.max(l.max,r.max),root.val));
}
寻找一个树中最大值和最小值（节点和值）
基本思路：
- 首先进行信息获取
- 需要左子树和右子树各自的最小值
- 左子树和右子树各自的最大值
- 整合信息；
- 小值为左子树的最小值、右子树的最小值，以及当前root的值的最小值。
- 树的最大值为左子树的最大值、右子树的最大值，以及当前root的值的最大值。
代码如下：
// 创建对象信息集
static class State{
int min;
int max;
public State(int min, int max) {
this.min = min;
this.max = max;
}
}
// 返回二叉树中的最大值和最小值
public static int[] getTreeBorderValue(TreeNode root){
State res = getAns(root);
return new int[]{res.min,res.max};
}
private static State getAns(TreeNode root) {
if(root == null) return new State(Integer.MAX_VALUE, Integer.MIN_VALUE);
// 获取左右子树的信息
State l = getAns(root.left);
State r = getAns(root.right);
// 整合信息
return new State(Math.min(Math.max(l.min,r.min),root.val),Math.max(Math.max(l.max,r.max),root.val));
}
public static void main(String[] args) {
TreeNode head1 = new TreeNode(1);
head1.left = new TreeNode(2);
head1.right = new TreeNode(3);
head1.left.left = new TreeNode(4);
head1.left.right = new TreeNode(5);
head1.right.left = new TreeNode(6);
head1.right.right = new TreeNode(7);
head1.left.left.left = new TreeNode(8);
head1.right.left.right = new TreeNode(9);
int[] arr1 = getTreeBorderValue(head1);
System.out.println(Arrays.toString(arr1));
TreeNode head2 = new TreeNode(1);
head2.left = new TreeNode(2);
head2.right = new TreeNode(3);
head2.right.left = new TreeNode(4);
head2.right.right = new TreeNode(5);
head2.right.left.left = new TreeNode(6);
head2.right.right.right = new TreeNode(7);
head2.right.left.left.left = new TreeNode(8);
head2.right.right.right.right = new TreeNode(9);
int[] arr2 = getTreeBorderValue(head2);
System.out.println(Arrays.toString(arr2));
}
求一颗二叉树上面的最远距离
题目描述：
在二叉树中，一个节点可以往上走也可以往下走，那么节点A总能走到节点B。
节点A走到节点B的距离为：A走到B最短路径上的节点个数。
求一颗二叉树上的最远距离。
基本思路：
- 首先获取有用的信息：
- 左右子树上的最远距离
- 左右子树各自的高度
- 整合相关的有用信息：
- 当前树中的最长距离为左子树的最长距离，右子树的最长距离以及当前左子树高度加上右子树高度加1中取最大。
代码如下：
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 创建对象信息集
static class State{
int maxLen; // 当前树的最大距离
int height; // 当前树的高度
State(int maxLen, int height) {
this.maxLen = maxLen;
this.height = height;
}
}
// 返回二叉树中的最大值和最小值
public static int getMaxLength(TreeNode root){
return getAns(root).maxLen;
}
private static State getAns(TreeNode root) {
if(root == null) return new State(0, 0);
// 获取左右子树的信息
State l = getAns(root.left);
State r = getAns(root.right);
// 整合信息
return new State(Math.max(Math.max(l.maxLen,r.maxLen),(l.height + r.height + 1)),
Math.max(l.height,r.height) + 1);
}
员工活跃度问题
问题描述：
员工活跃度
基本思路：
- 对于任何一个员工，都有两种可能性。情况一是该员工来的活跃度，情况二是该员工不来的活跃度。
- 那么结果只需要返回root员工，也就是大boos（上级是他自己）的来和不来两种情况下最大活跃度
- 如果大boss来， 那么当前结果为boss的活跃度 加上所有boos直系子员工不来的活跃度。
- 如果大boss不来，那么当前结果就是boss直系子员工来或不来活跃度的自大值。
- 最终比较来或者不来的活跃度，取最大值。
如果给出的matirx是以树结构呈现,则代码如下：
static class Node {
int huo; // 员工活跃度
List<Node> subNodes; // 下属员工活跃度集合
public Node(int huo){
this.huo = huo;
subNodes = new LinkedList<>();
}
}
// 创建对象信息集
static class State{
int lai_huo; // 当前员工来的活跃度
int bu_lai_huo; // 当前员工不来的活跃度
public State(int lai_huo, int bu_lai_huo) {
this.lai_huo = lai_huo;
this.bu_lai_huo = bu_lai_huo;
}
}
// 返回二叉树中的最大值和最小值
public static int getMaxHappy(Node root){
State boss = getAns(root);
return Math.max(boss.bu_lai_huo,boss.lai_huo);
}
private static State getAns(Node root) {
int lai_huo = root.huo;
int bu_lai_hup = 0;
for (int i = 0; i < root.subNodes.size(); i++) {
Node empty = root.subNodes.get(i);
State cur = getAns(empty);
lai_huo += cur.bu_lai_huo;
bu_lai_hup += Math.max(cur.lai_huo,cur.bu_lai_huo);
}
return new State(lai_huo,bu_lai_hup);
}
如果给出的是二维数组的结构，则用动态规划的思想取求解，代码如下：
// 获取最大的活跃值
public static int getMaxHappy(int[][] matrix){
// 创建一个二维数组存储活跃度信息
int[][] dp = new int[matrix.length][2];
// 第一个元素表示该员工来的活跃度，第二个元素表示员工不来的活跃度
boolean[] visited = new boolean[matrix.length]; // 创建数组，表示当前员工是否已经访问过
// 遍历martix，找出大boss的位置
int boss = 0;
for (int i = 0; i < matrix.length; i++) {
if(i == matrix[i][0]){
boss = i;
break;
}
}
// 进入递归返回最大
process(matrix,dp,visited,boss);
return Math.max(dp[boss][0],dp[boss][1]);
}
private static void process(int[][] matrix, int[][] dp, boolean[] visited, int boss) {
visited[boss] = true; // 计算boss的信息
dp[boss][0] = matrix[boss][1]; // 赋值活跃度
for (int i = 0; i < matrix.length; i++) {
if(matrix[i][0] == boss && !visited[boss]){
process(matrix, dp, visited, i);
dp[boss][0] += dp[i][1];
dp[boss][1] += Math.max(dp[i][0],dp[i][1]);
}
}
}
