精华内容
下载资源
问答
  • 第一次接触到树形dp的问题 本题对于某个结点进行分类讨论 1.当前结点拿,那么当前偷到的价值就是当前结点的价值加上左结点不拿时下面结点提供的价值和右节点不拿时下面结点提供的价值 2.当前结点不拿,那么当前偷到...

    题目链接
    在这里插入图片描述
    第一次接触到树形dp的问题
    本题对于某个结点进行分类讨论
    1.当前结点拿,那么当前偷到的价值就是当前结点的价值加上左结点不拿时下面结点提供的价值和右节点不拿时下面结点提供的价值
    2.当前结点不拿,那么当前偷到的价值就是左结点拿或者不拿的最大价值和右节点拿或者不拿的最大价值之和
    总结一下
    当前节点选择偷时,那么两个孩子节点就不能选择偷了
    当前节点选择不偷时,两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
    我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷,1 代表偷

       public int rob(TreeNode root) {
            int res[] = dp(root);
            return Math.max(res[0],res[1]);
        }
        public int[] dp(TreeNode root){
            if (root == null) return new int[2];
            // 分类讨论的标准是:当前结点偷或者不偷
            // 由于需要后序遍历,所以先计算左右子结点,然后计算当前结点的状态值
            int left[] = dp(root.left);
            int right[] = dp(root.right);
            int res[] = new int[2];
            // res[0]:以当前 node 为根结点的子树能够偷取的最大价值,规定 node 结点不偷
            // res[1]:以当前 node 为根结点的子树能够偷取的最大价值,规定 node 结点偷
            res[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
            res[1] = left[0]+right[0]+root.val;
            return res;
        }
    
    展开全文
  • 看了题解是树形dp,那么问题来了,为什么呢?这道题也没有什么最值,看起来距离之和是一个很固定的东西,一点都不动态。 其实我觉得,与其说是dp,不如说是递推。这里的中心思想就是从叶子往上推,处理距离 distSum...

    道题要求每个节点到其他所有节点的距离之和
    先考虑一个节点到其他所有节点的距离之和的问题。看到距离首先我想到的就是最短路,但是树上没啥最短路_(:з」∠)_
    然后我就没想出什么行之有效的方法_(:з」∠)_
    看了题解是树形dp,那么问题来了,为什么呢?这道题也没有什么最值,看起来距离之和是一个很固定的东西,一点都不动态。
    其实我觉得,与其说是dp,不如说是递推。这里的中心思想就是从叶子往上推,处理距离
    distSum[root] = sigma(distSum[root'sChild] + childSum[root'sChild]
    将这个递推用递归写出来

    void dfs(int node, int fa)
        {
            distSum[node] = 0;
            childNum[node] = 1;
            for (int i = 0; i < graph[node].size(); i++)
            {
                if (graph[node][i] == fa) continue;
                dfs(graph[node][i], node);
                childNum[node] += childNum[graph[node][i]];
                distSum[node] += distSum[graph[node][i]] + childNum[graph[node][i]];
            }
        }
    
    

    解决了这个问题之后,你可以把所有点都当做root跑一遍dfs,但是你看看根的儿子,它到所有节点的距离之和根本不用重新算,可以从父节点推出来。
    distSum[node] = distSum[fa] - childNum[node] + (N - childNum[node]);

    完整代码:

    class Solution {
    public:
        vector<vector<int>> graph;
        vector<int> distSum, childNum;
    
        void dfs(int node, int fa)
        {
            distSum[node] = 0;
            childNum[node] = 1;
            for (int i = 0; i < graph[node].size(); i++)
            {
                if (graph[node][i] == fa) continue;
                dfs(graph[node][i], node);
                childNum[node] += childNum[graph[node][i]];
                distSum[node] += distSum[graph[node][i]] + childNum[graph[node][i]];
            }
        }
    
        void changeRoot(int node, int fa)
        {
            if (fa != -1)
            {
                distSum[node] = distSum[fa] - childNum[node] + (graph.size() - childNum[node]);
            }
            for (int i = 0; i < graph[node].size(); i++)
            {
                if (graph[node][i] == fa) continue;
                changeRoot(graph[node][i], node);
            }
        }
    
        vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
            graph.resize(N, {});
            childNum.resize(N, 0);
            distSum.resize(N, 0);
            for (int i = 0; i < edges.size(); i++)
            {
                graph[edges[i][0]].push_back(edges[i][1]);
                graph[edges[i][1]].push_back(edges[i][0]);
            }
            dfs(0, -1);
            changeRoot(0, -1);
            return distSum;
        }
    };
    
    

    另,看到了两篇蛮不错的树形dp讲解
    这篇的重点是树形dp在设状态转移方程时都可以用f[i][]表示i这颗子树怎么怎么样的最优解,实现时一般都是用子树更新父亲
    这篇的重点是给出了树形dp的解题步骤:1、判断是否是树规题 2、建树 3、写树规方程

    展开全文
  • 用f(root)表示从root节点出发能盗取的最高金额 f(root) = max(f(root->left)+f(root->right), root->val + f(root->left->left)+f(root->left->right) + f(root->right->...

    用f(root)表示从root节点出发能盗取的最高金额

    f(root) = max(f(root->left)+f(root->right),  root->val +  f(root->left->left)+f(root->left->right) + f(root->right->left) + f(root->right->right))

    如果直接这样搜索,为有大量的重复搜索,所以要用hashmap记录状态
     

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        unordered_map<TreeNode*,int> hashmap;
        int rob(TreeNode* root) {
            // rob(root) 表示从根节点出发的最高金额
            if(root==NULL) return 0;
            if(hashmap.count(root)) return hashmap[root];
            int money = root->val;
            if(root->left){
                money += rob(root->left->left)+rob(root->left->right);
            }
            if(root->right){
                money += rob(root->right->right)+rob(root->right->left);
            }
            return max(money,rob(root->left)+rob(root->right));
        }
    };

    记忆话优化

    class Solution {
    public:
        unordered_map<TreeNode*,int> hashmap;
        int rob(TreeNode* root) {
            // rob(root) 表示从根节点出发的最高金额
            if(root==NULL) return 0;
            if(hashmap.count(root)) return hashmap[root];
            int money = root->val;
            if(root->left){
                money += rob(root->left->left)+rob(root->left->right);
            }
            if(root->right){
                money += rob(root->right->right)+rob(root->right->left);
            }
            int val = max(money,rob(root->left)+rob(root->right));
            hashmap[root] = val;
            return val;
        }
    };

     

    展开全文
  • 给定一棵有 n 个结点的二叉树,你的任务是检查是否可以通过去掉上的一条边将分成两棵,且这两棵结点之和相等。 样例 1: 输入: 5 / \ 10 10 / \ 2 3 输出: True 解释: 5 / 10 和: 15 10 / \ 2...

    文章目录

    1. 题目

    给定一棵有 n 个结点的二叉树,你的任务是检查是否可以通过去掉树上的一条边将树分成两棵,且这两棵树结点之和相等。

    样例 1:
    输入:     
        5
       / \
      10 10
        /  \
       2   3
    输出: True
    解释: 
        5
       / 
      10: 15
    
       10
      /  \
     2    3: 15
     
    
    样例 2:
    输入:     
        1
       / \
      2  10
        /  \
       2   20
    输出: False
    解释: 无法通过移除一条树边将这棵树划分成结点之和相等的两棵子树。
     
    注释 :
    树上结点的权值范围 [-100000, 100000]1 <= n <= 10000
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/equal-tree-partition
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    2. 解题

    在这里插入图片描述

    • 自底向上求得每个节点的子树和,更新于节点的 val
    • 遍历检查+剪枝,共计2次遍历
    class Solution {
    	bool found = false;
    	int allsum;
    public:
        bool checkEqualTree(TreeNode* root) {
        	allsum = sum(root);
            if(allsum&1) return false;//奇数不可分
        	check(root);
        	return found;
        }
        int sum(TreeNode* root)
        {
        	if(!root) return 0;
        	int l = sum(root->left);
        	int r = sum(root->right);
        	return root->val += l+r;
        }
        bool check(TreeNode* root)
        {
        	if(!root) return false;
            if(found) return true;
        	if(root->left && allsum == 2*root->left->val)
        		return found = true;
        	if(root->right && allsum == 2*root->right->val)
        		return found = true;
        	return check(root->left) || check(root->right);
        }
    };
    

    40 ms 31.9 MB


    我的CSDN博客地址 https://michael.blog.csdn.net/

    长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
    Michael阿明

    展开全文
  • 关于 树形dp 套路,可以参考我的另一篇博客:左神算法:找到二叉树中的最大搜索二叉子树(Java版) 下面简述本题思路: 首先,如何判断一个节点 head 是否是 p、q 的公共祖先?只需要用二分查找的方式,判断以 head...
  • 由于要考虑每个节点是否放置摄像头,又要考虑是否一棵都能被覆盖到。 状态a:当前节点安装相机的时候,且能整棵被覆盖到需要的最少相机数 状态b: 当前节点不需要安装相机,但是能被覆盖到这棵的时候,需要的...
  • 834. 中距离之和 难度困难143收藏分享切换为英文接收动态反馈 给定一个无向、连通的中有N个标记为0...N-1的节点以及N-1条边。 第i条边连接节点edges[i][0]和edges[i][1]。 返回一个表示节点i与其他所有...
  • 树形DP 实现 码前思考 由于之前做过了⭐LeetCode 124. Binary Tree Maximum Path Sum,这道题的思想和它是一样的,所以就没多想了。 代码实现 //我记得我之前做过一道“剥洋葱的题” //到时候回去看看 //这道题...
  • 中距离之和 这道题目,很容易想到O(n2)O(n^2)O(n2)的做法。 如何只求出到一个点的距离: 状态:f[x]f[x]f[x]就表示所有的点到x的距离; DP方程: f[x]=f[y1]+f[y2]+……+f[yk]+……+s[y1]+s[y2]+……+s[yk]+……f...
  • 题目描述: 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。...来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/house-robber-ii
  • 对于树形DP的问题,其实说白了,我认为树形DP问题就是在树结构上,求解最优化问题。 有了上面的理解,树形DP问题的解题套路就是以当前子树根结点,结合当前子树根结点的左子树和当前子树根结点的右子树进行分情况...
  • 题目连接:Leetcode 124 Binary Tree Maximum Path Sum解题思路:每次递归遍历,返回结点单向的最大值,遍历过程中维护最大值。/** * Definition for a binary tree node. * struct TreeNode { * int val; * ...
  • 树形DP 实现 码前思考 看见最优化的问题,我们基本上是要思考一下能不能使用DP来进行求解,虽然可能有时不行,但是一定要先思考能不能用DP,不能没有尝试就放弃DP思想; 这其实是一类非常常见的DP思想,为什么说...
  • LeetCode #12 双周赛 5097. 力扣排行榜 题目:设计一个排行榜,满足插入、前缀和、排序。 分析:数据范围很小,用不到 logn 的数据结构,直接暴力即可。 用 mapmapmap 存编号对应成绩,每次查询暴力排序找前 k 和。 ...
  • 本题中,路径被定义为一条从中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。 该路径至少包含一个节点,且不一定经过根节点。 解法: 题意类似是求的直径,只不过计算的是路径的最大点权和. 做法是...
  • 思路:如果选择的当前节点就不选择左右孩子节点,为了避免对节点重复dfs超时,使用map记录已经访问过的节点。 代码如下: class Solution { public: map<TreeNode *, int> mp; int dfs(TreeNode* tree, ...
  • 本题中,路径被定义为一条从中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 看到这题一开始整体的思路还是递归,对左右子树分别递归处理。如果dfs(root)表示 ...
  • 树形dp: 维护两个dp,dp1和dp2都以当前节点为根的子树,其中dp1是偷当前节点最大值,dp2是不偷当前节点的最大值,深度优先搜索,先求子树再向上,最后结果是max(dp1[root],dp2[root]) /** * Definition for a...

空空如也

空空如也

1 2 3 4 5
收藏数 81
精华内容 32
关键字:

leetcode树形dp