class078 树型dp-上【算法】-阿里云开发者社区

class078 树型dp-上【算法】

算法讲解078【必备】树型dp-上

code1 333. 最大 BST 子树

// 最大BST子树

// 给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小

// 其中，最大指的是子树节点数最多的

// 二叉搜索树（BST）中的所有节点都具备以下属性：

// 左子树的值小于其父（根）节点的值

// 右子树的值大于其父（根）节点的值

// 注意：子树必须包含其所有后代

// 测试链接 : https://leetcode.cn/problems/largest-bst-subtree/

树形dp：

x头整树的maxBstSize

不含x：max(左树maxBstSize,右树maxBstSize)

包含x：左树isBst,右树isBst,左树max,右树min，如果max<x<min，返回：左树maxBstSize+右树maxBstSize+1

所以需要返回值(maxBstSize,isBst,max,min)

空树返回[0,true,MAX,MIN]

类似于后序遍历：得到孩子的返回值，再整合自己的返回值，最后返回给上层

package class078;
// 最大BST子树
// 给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小
// 其中，最大指的是子树节点数最多的
// 二叉搜索树（BST）中的所有节点都具备以下属性：
// 左子树的值小于其父（根）节点的值
// 右子树的值大于其父（根）节点的值
// 注意：子树必须包含其所有后代
// 测试链接 : https://leetcode.cn/problems/largest-bst-subtree/
public class Code01_LargestBstSubtree {
  // 不要提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交如下的方法
  public static int largestBSTSubtree(TreeNode root) {
    return f(root).maxBstSize;
  }
  public static class Info {
    public long max;
    public long min;
    public boolean isBst;
    public int maxBstSize;
    public Info(long a, long b, boolean c, int d) {
      max = a;
      min = b;
      isBst = c;
      maxBstSize = d;
    }
  }
  public static Info f(TreeNode x) {
    if (x == null) {
      return new Info(Long.MIN_VALUE, Long.MAX_VALUE, true, 0);
    }
    Info infol = f(x.left);
    Info infor = f(x.right);
    // 左 4信息
    // 右 4信息
    // x 整合出4信息返回
    long max = Math.max(x.val, Math.max(infol.max, infor.max));
    long min = Math.min(x.val, Math.min(infol.min, infor.min));
    boolean isBst = infol.isBst && infor.isBst && infol.max < x.val && x.val < infor.min;
    int maxBSTSize;
    if (isBst) {
      maxBSTSize = infol.maxBstSize + infor.maxBstSize + 1;
    } else {
      maxBSTSize = Math.max(infol.maxBstSize, infor.maxBstSize);
    }
    return new Info(max, min, isBst, maxBSTSize);
  }
}

code2 1373. 二叉搜索子树的最大键值和

// 二叉搜索子树的最大键值和

// 给你一棵以 root 为根的二叉树

// 请你返回任意二叉搜索子树的最大键值和

// 二叉搜索树的定义如下：

// 任意节点的左子树中的键值都小于此节点的键值

// 任意节点的右子树中的键值都大于此节点的键值

// 任意节点的左子树和右子树都是二叉搜索树

// 测试链接 : https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/

x头整树的maxBstSum

不含x：max(左maxBstSum，右maxBstSum)

包含x：左isBst，右isBst，左max，右min，如果max<x<min返回左sum+右sum+x.val

整合（max,min,sum,isBst,maxBstSum）

空树返回(MAX,MIN,0,true,0)

package class078;
// 二叉搜索子树的最大键值和
// 给你一棵以 root 为根的二叉树
// 请你返回 任意 二叉搜索子树的最大键值和
// 二叉搜索树的定义如下：
// 任意节点的左子树中的键值都 小于 此节点的键值
// 任意节点的右子树中的键值都 大于 此节点的键值
// 任意节点的左子树和右子树都是二叉搜索树
// 测试链接 : https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/
public class Code02_MaximumSumBst {
  // 不要提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交如下的方法
  public static int maxSumBST(TreeNode root) {
    return f(root).maxBstSum;
  }
  public static class Info {
    // 为什么这里的max和min是int类型？
    // 因为题目的数据量规定，
    // 节点值在[-4 * 10^4，4 * 10^4]范围
    // 所以int类型的最小值和最大值就够用了
    // 不需要用long类型
    public int max;
    public int min;
    public int sum;
    public boolean isBst;
    public int maxBstSum;
    public Info(int a, int b, int c, boolean d, int e) {
      max = a;
      min = b;
      sum = c;
      isBst = d;
      maxBstSum = e;
    }
  }
  public static Info f(TreeNode x) {
    if (x == null) {
      return new Info(Integer.MIN_VALUE, Integer.MAX_VALUE, 0, true, 0);
    }
    Info infol = f(x.left);
    Info infor = f(x.right);
    int max = Math.max(x.val, Math.max(infol.max, infor.max));
    int min = Math.min(x.val, Math.min(infol.min, infor.min));
    int sum = infol.sum + infor.sum + x.val;
    boolean isBst = infol.isBst && infor.isBst && infol.max < x.val && x.val < infor.min;
    int maxBstSum = Math.max(infol.maxBstSum, infor.maxBstSum);
    if (isBst) {
      maxBstSum = Math.max(maxBstSum, sum);
    }
    return new Info(max, min, sum, isBst, maxBstSum);
  }
}

code3 543. 二叉树的直径

// 二叉树的直径

// 给你一棵二叉树的根节点，返回该树的直径

// 二叉树的直径是指树中任意两个节点之间最长路径的长度

// 这条路径可能经过也可能不经过根节点 root

// 两节点之间路径的长度由它们之间边数表示

// 测试链接 : https://leetcode.cn/problems/diameter-of-binary-tree/

x头的直径

不含x：max(左直径，右直径)

包含x：左最大深度+右最大深度（不加1，边比点数量少1）

返回(直径，高度)

空树返回(0,0)

package class078;
// 二叉树的直径
// 给你一棵二叉树的根节点，返回该树的直径
// 二叉树的 直径 是指树中任意两个节点之间最长路径的长度
// 这条路径可能经过也可能不经过根节点 root
// 两节点之间路径的 长度 由它们之间边数表示
// 测试链接 : https://leetcode.cn/problems/diameter-of-binary-tree/
public class Code03_DiameterOfBinaryTree {
  // 不要提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交如下的方法
  public static int diameterOfBinaryTree(TreeNode root) {
    return f(root).diameter;
  }
  public static class Info {
    public int diameter;
    public int height;
    public Info(int a, int b) {
      diameter = a;
      height = b;
    }
  }
  public static Info f(TreeNode x) {
    if (x == null) {
      return new Info(0, 0);
    }
    Info leftInfo = f(x.left);
    Info rightInfo = f(x.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    int diameter = Math.max(leftInfo.diameter, rightInfo.diameter);
    diameter = Math.max(diameter, leftInfo.height + rightInfo.height);
    return new Info(diameter, height);
  }
}

code4 979. 在二叉树中分配硬币

// 在二叉树中分配硬币

// 给你一个有 n 个结点的二叉树的根结点 root

// 其中树中每个结点 node 都对应有 node.val 枚硬币

// 整棵树上一共有 n 枚硬币

// 在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点

// 移动可以是从父结点到子结点，或者从子结点移动到父结点

// 返回使每个结点上只有一枚硬币所需的最少移动次数

// 测试链接 : https://leetcode.cn/problems/distribute-coins-in-binary-tree/

以x为头的树，几部

左步数+右步数+|左结点树-左硬币数|+|右结点树-右硬币数|

返回（步数，结点和，硬币和）

package class078;
// 在二叉树中分配硬币
// 给你一个有 n 个结点的二叉树的根结点 root
// 其中树中每个结点 node 都对应有 node.val 枚硬币
// 整棵树上一共有 n 枚硬币
// 在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点
// 移动可以是从父结点到子结点，或者从子结点移动到父结点
// 返回使每个结点上 只有 一枚硬币所需的 最少 移动次数
// 测试链接 : https://leetcode.cn/problems/distribute-coins-in-binary-tree/
public class Code04_DistributeCoins {
  // 不要提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交如下的方法
  public static int distributeCoins(TreeNode root) {
    return f(root).move;
  }
  public static class Info {
    public int cnt;
    public int sum;
    public int move;
    public Info(int a, int b, int c) {
      cnt = a;
      sum = b;
      move = c;
    }
  }
  public static Info f(TreeNode x) {
    if (x == null) {
      return new Info(0, 0, 0);
    }
    Info infol = f(x.left);
    Info infor = f(x.right);
    int cnts = infol.cnt + infor.cnt + 1;
    int sums = infol.sum + infor.sum + x.val;
    int moves = infol.move + infor.move + Math.abs(infol.cnt - infol.sum) + Math.abs(infor.cnt - infor.sum);
    return new Info(cnts, sums, moves);
  }
}

code5 P1352 没有上司的舞会

// 没有上司的舞会

// 某大学有n个职员，编号为1…n

// 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树

// 父结点就是子结点的直接上司

// 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数

// 但是如果某个职员的直接上司来参加舞会了

// 那么这个职员就无论如何也不肯来参加舞会了

// 所以请你编程计算邀请哪些职员可以使快乐指数最大

// 返回最大的快乐指数。

// 测试链接 : https://www.luogu.com.cn/problem/P1352

// 本题和讲解037的题目7类似

// 链式链接 : https://leetcode.cn/problems/house-robber-iii/

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

以x为头的数

x来：x+以a为头的来数+以b为头的来数+以c为头的来数+…

x不来：以a为头的数max(来，不来）+以b为头的数max(来，不来）+以c为头的数max(来，不来）

整合返回（来，不来）

package class078;
// 没有上司的舞会
// 某大学有n个职员，编号为1...n
// 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树
// 父结点就是子结点的直接上司
// 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 
// 但是如果某个职员的直接上司来参加舞会了
// 那么这个职员就无论如何也不肯来参加舞会了
// 所以请你编程计算邀请哪些职员可以使快乐指数最大
// 返回最大的快乐指数。
// 测试链接 : https://www.luogu.com.cn/problem/P1352
// 本题和讲解037的题目7类似
// 链式链接 : https://leetcode.cn/problems/house-robber-iii/
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Code05_Dancing {
  public static int MAXN = 6001;
  public static int[] nums = new int[MAXN];
  public static boolean[] boss = new boolean[MAXN];
  // 链式前向星建图
  public static int[] head = new int[MAXN];
  public static int[] next = new int[MAXN];
  public static int[] to = new int[MAXN];
  public static int cnt;
  // 动态规划表
  // no[i] : i为头的整棵树，在i不来的情况下，整棵树能得到的最大快乐值
  public static int[] no = new int[MAXN];
  // no[i] : i为头的整棵树，在i来的情况下，整棵树能得到的最大快乐值
  public static int[] yes = new int[MAXN];
  public static int n, h;
  public static void build(int n) {
    Arrays.fill(boss, 1, n + 1, true);
    Arrays.fill(head, 1, n + 1, 0);
    cnt = 1;
  }
  public static void addEdge(int u, int v) {
    next[cnt] = head[u];
    to[cnt] = v;
    head[u] = cnt++;
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      build(n);
      for (int i = 1; i <= n; i++) {
        in.nextToken();
        nums[i] = (int) in.nval;
      }
      for (int i = 1, low, high; i < n; i++) {
        in.nextToken();
        low = (int) in.nval;
        in.nextToken();
        high = (int) in.nval;
        addEdge(high, low);
        boss[low] = false;
      }
      for (int i = 1; i <= n; i++) {
        if (boss[i]) {
          h = i;
          break;
        }
      }
      f(h);
      out.println(Math.max(no[h], yes[h]));
    }
    out.flush();
    out.close();
    br.close();
  }
  public static void f(int u) {
    no[u] = 0;
    yes[u] = nums[u];
    for (int ei = head[u], v; ei > 0; ei = next[ei]) {
      v = to[ei];
      f(v);
      no[u] += Math.max(no[v], yes[v]);
      yes[u] += no[v];
    }
  }
}

code6 968. 监控二叉树

// 监控二叉树

// 给定一个二叉树，我们在树的节点上安装摄像头

// 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象

// 计算监控树的所有节点所需的最小摄像头数量

// 测试链接 : https://leetcode.cn/problems/binary-tree-cameras/

三个状态

0：x无覆盖，但下方全覆盖了

1：x有覆盖，x上无相机

2：x有覆盖，x上有相机

左右有任何1个0，x放回2

左右都是1，x放回0

左右有12 21 22，x放回0

空树返回1

package class078;
// 监控二叉树
// 给定一个二叉树，我们在树的节点上安装摄像头
// 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象
// 计算监控树的所有节点所需的最小摄像头数量
// 测试链接 : https://leetcode.cn/problems/binary-tree-cameras/
public class Code06_BinaryTreeCameras {
  // 不要提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交如下的方法
  public int minCameraCover(TreeNode root) {
    ans = 0;
    if (f(root) == 0) {
      ans++;
    }
    return ans;
  }
  // 遍历过程中一旦需要放置相机，ans++
  public static int ans;
  // 递归含义
  // 假设x上方一定有父亲的情况下，这个假设很重要
  // x为头的整棵树，最终想都覆盖，
  // 并且想使用最少的摄像头，x应该是什么样的状态
  // 返回值含义
  // 0: x是无覆盖的状态，x下方的节点都已经被覆盖
  // 1: x是覆盖状态，x上没摄像头，x下方的节点都已经被覆盖
  // 2: x是覆盖状态，x上有摄像头，x下方的节点都已经被覆盖
  private int f(TreeNode x) {
    if (x == null) {
      return 1;
    }
    int left = f(x.left);
    int right = f(x.right);
    if (left == 0 || right == 0) {
      ans++;
      return 2;
    }
    if (left == 1 && right == 1) {
      return 0;
    }
    return 1;
  }
}

code7 437. 路径总和 III

// 路径总和 III

// 给定一个二叉树的根节点 root ，和一个整数 targetSum

// 求该二叉树里节点值之和等于 targetSum 的路径的数目

// 路径不需要从根节点开始，也不需要在叶子节点结束

// 但是路径方向必须是向下的（只能从父节点到子节点）

// 测试链接 : https://leetcode.cn/problems/path-sum-iii/

sum : 从头节点出发，来到x的时候，上方累加和是多少

路径必须以x作为结尾，路径累加和是target的路径数量，累加到全局变量ans上

package class078;
import java.util.HashMap;
// 路径总和 III
// 给定一个二叉树的根节点 root ，和一个整数 targetSum
// 求该二叉树里节点值之和等于 targetSum 的 路径 的数目
// 路径 不需要从根节点开始，也不需要在叶子节点结束
// 但是路径方向必须是向下的（只能从父节点到子节点）
// 测试链接 : https://leetcode.cn/problems/path-sum-iii/
public class Code07_PathSumIII {
  // 不要提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交如下的方法
  public static int pathSum(TreeNode root, int sum) {
    HashMap<Long, Integer> presum = new HashMap<>();
    presum.put(0L, 1);
    ans = 0;
    f(root, sum, 0, presum);
    return ans;
  }
  public static int ans;
  // sum : 从头节点出发，来到x的时候，上方累加和是多少
  // 路径必须以x作为结尾，路径累加和是target的路径数量，累加到全局变量ans上
  public static void f(TreeNode x, int target, long sum, HashMap<Long, Integer> presum) {
    if (x != null) {
      sum += x.val; // 从头节点出发一路走到x的整体累加和
      ans += presum.getOrDefault(sum - target, 0);
      presum.put(sum, presum.getOrDefault(sum, 0) + 1);
      f(x.left, target, sum, presum);
      f(x.right, target, sum, presum);
      presum.put(sum, presum.get(sum) - 1);
    }
  }
}

class078 树型dp-上【算法】