首页 > 其他分享 >力扣刷题记录: 1339. 分裂二叉树的最大乘积

力扣刷题记录: 1339. 分裂二叉树的最大乘积

时间:2024-06-13 11:29:14浏览次数:20  
标签:1339 sum long 力扣 record 二叉树 return total root

        本题是第174场周赛的 Q3,LC竞赛分为1675.

方法一. 递归(超时)

        单纯使用递归对每一个节点进行遍历,代码如下:

class Solution {
    long long ans = -1;
public:
    int maxProduct(TreeNode* root) {
        long long total_sum = sum(root);

        dfs(root,total_sum);

        return ans%(int)(1e9+7);
    }

    long long sum(TreeNode* root){
        if(root == NULL) return 0;

        return root->val+sum(root->left)+sum(root->right);
    }

    void dfs(TreeNode* root,long long total_sum){
        if(!root) return;

        long long a1 = sum(root);
        long long a2 = total_sum-a1;
        ans = max(a1*a2,ans);

        dfs(root->left,total_sum);
        dfs(root->right,total_sum);
    }
};

方法二. 后序遍历+记忆化搜索(时间超过 11.89% cpp用户)

        后序遍历+记忆化搜索可以让父节点直接用到子节点的结果,从而减少递归调用。代码如下:

class Solution {
    long long ans = -1;
public:
    int maxProduct(TreeNode* root) {
        long long total_sum = sum(root);
        map<TreeNode*,long long> record;
        dfs(root,total_sum,record);

        return ans%(int)(1e9+7);
    }

    long long sum(TreeNode* root){
        if(root == NULL) return 0;

        return root->val+sum(root->left)+sum(root->right);
    }

    void dfs(TreeNode* root,long long total_sum,map<TreeNode*,long long>& record ){
        if(!root) return;

        dfs(root->left,total_sum,record);
        dfs(root->right,total_sum,record);
        long long a1,a2;
        if(record.count(root->left)==1){
            a1 = record[root->left];
        }
        else
            a1 = sum(root->left);
        
        if(record.count(root->right)==1){
            a2 = record[root->right];
        }
        else
            a2 = sum(root->right);
        
        long long sum_tmp = a1 + a2 + root->val;
        record[root] = sum_tmp;
        ans = max(ans,sum_tmp*(total_sum-sum_tmp));
        return;
    }
};

标签:1339,sum,long,力扣,record,二叉树,return,total,root
From: https://blog.csdn.net/Bright_Brilliant/article/details/139645226

相关文章

  • 力扣刷题记录: 1424. 对角线遍历Ⅱ
        本题是第182场周赛的Q3,LC竞赛分为1780。方法一.利用反对角线性质    在同一条反对角线上的元素的i+j值是相同的,同时,根据遍历的方式可知,i值越大的元素在同一条反对角线之中越先被遍历,i+j值越小的反对角线越早被遍历。考虑采用有序的map对i+j......
  • 【动态规划】| 路径问题之不同路径II 力扣63
    ......
  • 力扣第198题“打家劫舍”
    关注微信公众号数据分析螺丝钉免费领取价值万元的python/java/商业分析/数据结构与算法学习资料在本篇文章中,我们将详细解读力扣第198题“打家劫舍”。通过学习本篇文章,读者将掌握如何使用动态规划来解决这一问题,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以......
  • 【力扣真题】3.哈希表|算法真题程序设计数据结构考研保研复试机试面试秋招春招蓝桥杯
    242.有效的字母异位词给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。示例1:输入:s=“anagram”,t=“nagaram”输出:true示例2:输入:s=“rat”,t=“car”输出:false说明:你可以假设字符串只包含小写字母。力扣题目链接思......
  • Day49 代码随想录打卡|二叉树篇---二叉搜索树中的搜索
    题目(leecodeT700):给定二叉搜索树(BST)的根节点 root 和一个整数值 val。你需要在BST中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在,则返回 null 。方法:递归法:本题考察了二叉搜索树的特性,二叉搜索树指的是在这个二叉树中,他的每一个根节点......
  • 验证二叉搜索树-力扣
    第一次做这道题时,想的解法是递归去判断比较左节点小于中间节点,右节点大于中间节点,而这恰恰进入了陷阱,这道题不仅仅是判断子树是否左节点小于中间节点,右节点大于中间节点;要比较的是左子树所有节点小于中间节点,右子树所有节点大于中间节点。附上错误代码:classSolution{pu......
  • 力扣面试题 02.07. 链表相交
    一 题目:二思路:本题介绍两种思路解题,个人推荐思路一快速好理解 思路一: 1.先把其中一个链表的值变成负数 2.遍历另一个链表第一个出现负数的值就是交点 3.还原被改的链表 思路二:1.先用第一个链表的头节点head1搜索指针q遍历第一个链表直到为空,再把q放到head2......
  • 五分钟“手撕”二叉树
    代码放开头,供大家查阅。但是对于树来说,更重要的是理解树的概念,树的概念很多,题却是千篇一律,这篇博客详细的讲解了概念,看完必有很大的收获。 目录一、实现代码二、什么是树三、树的重要概念四、什么是二叉树 二叉树概念:特殊的二叉树: 1.满二叉树:2.完全二叉树:......
  • 路径总和-力扣
    本题想到的解法是对二叉树进行深度搜索,并记录路径和,当节点为叶子节点时,将路径和与目标值进行判断,如果相等则返回true,否则返回false,最后返回左右子树或的值即可,因为只需有一条满足条件就可以。/***Definitionforabinarytreenode.*structTreeNode{*intv......
  • 左叶子之和-力扣
    本题计算二叉树的左叶子之和,使用后序遍历的顺序对二叉树进行深度搜索,关键点在于,对左叶子节点的值的操作上,需要在左叶子节点的父节点进行。/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right......