078树型dp

树
头结点没有父亲 其他节点只有一个父亲的有向无环图，直观理解为发散状
在树上，从头结点出发到任何节点的路径是唯一的，不管是二叉树还是多叉树

树型dp是指在树上做动态规划，依赖关系比一般的动态规划简单
因为绝大部分都是父依赖子

套路
1 分析父树得到答案需要子树的哪些信息
2 把子树信息的全集定义成递归返回值
3 通过递归让子树返回全集信息
4 整合子树的全集信息得到父树的全集信息并且返回

题目一

// 最大BST子树
// 给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小
// 其中，最大指的是子树节点数最多的
// 二叉搜索树（BST）中的所有节点都具备以下属性：
// 左子树的值小于其父（根）节点的值
// 右子树的值大于其父（根）节点的值
// 注意：子树必须包含其所有后代
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);
	}

题目二

// 二叉搜索子树的最大键值和
// 给你一棵以 root 为根的二叉树
// 请你返回 任意 二叉搜索子树的最大键值和
// 测试链接 : https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/
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);
	}

题目三

// 二叉树的直径
// 给你一棵二叉树的根节点，返回该树的直径
// 二叉树的 直径 是指树中任意两个节点之间最长路径的长度
// 这条路径可能经过也可能不经过根节点 root
// 两节点之间路径的 长度 由它们之间边数表示
// 测试链接 : https://leetcode.cn/problems/diameter-of-binary-tree/
// 提交如下的方法
	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);
	}

题目四

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);
	}