前置知识: 讲解017、讲解018、讲解036、讲解037 - 二叉树基础内容 讲解059 - 建图、链式前向星建图、拓扑排序 讲解060 - 拓扑排序的扩展技巧，讲的题就是DAG图上的动态规划 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

本节课讲述最常见的树型dp问题，详解树型dp的解题套路

下节课会讲述树型dp利用dfn序的内容

注意： 讲解060-拓扑排序的扩展技巧，DAG图上做动态规划（Directed Acyclic Graph），不要跳过 树型dp中有关 换根dp 的内容，将放在【扩展】课程阶段讲述

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

树型dp在树上做动态规划，依赖关系比一般动态规划简单 因为绝大部分多数都是父依赖子 只是依赖关系简单，不代表题目简单

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

题目1 最大BST子树 给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小 其中，最大指的是子树节点数最多的 二叉搜索树（BST）中的所有节点都具备以下属性： 左子树的值小于其父（根）节点的值 右子树的值大于其父（根）节点的值 注意：子树必须包含其所有后代 测试链接 : https://leetcode.cn/problems/largest-bst-subtree/

题目2 二叉搜索子树的最大键值和 给你一棵以 root 为根的二叉树 请你返回 任意 二叉搜索子树的最大键值和 二叉搜索树的定义如下： 任意节点的左子树中的键值都 小于 此节点的键值 任意节点的右子树中的键值都 大于 此节点的键值 任意节点的左子树和右子树都是二叉搜索树 测试链接 : https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/

题目3 二叉树的直径 给你一棵二叉树的根节点，返回该树的直径 二叉树的 直径 是指树中任意两个节点之间最长路径的长度 这条路径可能经过也可能不经过根节点 root 两节点之间路径的 长度 由它们之间边数表示 测试链接 : https://leetcode.cn/problems/diameter-of-binary-tree/

题目4 在二叉树中分配硬币 给你一个有 n 个结点的二叉树的根结点 root 其中树中每个结点 node 都对应有 node.val 枚硬币 整棵树上一共有 n 枚硬币 在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点 移动可以是从父结点到子结点，或者从子结点移动到父结点 返回使每个结点上 只有 一枚硬币所需的 最少 移动次数 测试链接 : https://leetcode.cn/problems/distribute-coins-in-binary-tree/

题目5 没有上司的舞会 某大学有n个职员，编号为1...n 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树 父结点就是子结点的直接上司 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 但是如果某个职员的直接上司来参加舞会了 那么这个职员就无论如何也不肯来参加舞会了 所以请你编程计算邀请哪些职员可以使快乐指数最大，返回最大的快乐指数。 测试链接 : https://www.luogu.com.cn/problem/P1352 本题和讲解037的题目7类似 链式链接 : https://leetcode.cn/problems/house-robber-iii/

题目6 监控二叉树 给定一个二叉树，我们在树的节点上安装摄像头 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象 计算监控树的所有节点所需的最小摄像头数量 测试链接 : https://leetcode.cn/problems/binary-tree-cameras/

题目7 路径总和 III 给定一个二叉树的根节点 root ，和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目 路径 不需要从根节点开始，也不需要在叶子节点结束 但是路径方向必须是向下的（只能从父节点到子节点） 测试链接 : https://leetcode.cn/problems/path-sum-iii/

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com