979. 在二叉树中分配硬币(力扣)

这篇具有很好参考价值的文章主要介绍了979. 在二叉树中分配硬币(力扣)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给你一个有 n 个结点的二叉树的根结点 root ,其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。

在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点,或者从子结点移动到父结点。

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

示例 1:
979. 在二叉树中分配硬币(力扣),leetcode题目,leetcode,算法,职场和发展

输入:root = [3,0,0]
输出:2
解释:一枚硬币从根结点移动到左子结点,一枚硬币从根结点移动到右子结点。

树中节点的数目为 n
1 <= n <= 100
0 <= Node.val <= n
所有 Node.val 的值之和是 n

一题一解:DFS(java)

思路

我们要寻找每个节点判断是否,有多余的或者不足的硬币,如果有此时我们应该给答案加上差值,因为不足和多余都是要移动硬币的情况,所以对于答案来说,视为一种情况,都为加在答案ans上。
979. 在二叉树中分配硬币(力扣),leetcode题目,leetcode,算法,职场和发展

步骤解析

我们从根节点开始遍历,如上图所示,
值为3的父节点因为没有左节点所以,左节点返回的数组是int []{0,0};

当我们遍历到右节点值为3的时候,在往下遍历时候,值为3的节点是没有左右节点的所以,值为3节点返回的数组int[]{coins,nodes}是int[]{3,1} 那么答案经过计算ans+=Math.abs(coins-nodes);值就为2。

那么值为3的父节点,返回的数组是以它所形成子树的硬币数和节点数总值 ,
int[]{3,2} ,那么答案经过计算,值就为3

其实叶子节点也就看作了是子树,只是特殊的子树,返回的还是以叶子节点所形成的子树总的硬币数和节点数。

那么返回给它的父节点也就是返回给值为1的节点,它左节点返回的是int[]{3,2},当遍历它右节点的时候,因为右节点是叶子节点且没有值,所以它所形成的子树总的硬币coins=0,节点node=1,返回数组为int[]{0,1},那么答案经过计算,值就为4。
所以根节点的左节点形成的子树返回的是int[]{3,2},右节点形成的子树返回的是int[]{0,1},根节点计算之后,coins=3,nodes=3,答案ans不用变化。所以结果是4

测试代码


class Solution{
    private  int ans=0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return ans;
    }
   private int[]  dfs(TreeNode treeNode){
        //当走到叶子节点的时候左右节点所形成的子树没有值
        if (treeNode==null)return new int[]{0,0};
        //遍历当前节点的左节点,返回当前左节点所形成的子树的硬币数和节点数
        int[] left=dfs(treeNode.left);
       //遍历当前节点的右节点,返回当前右节点所形成的子树的硬币数和节点数
        int[] right=dfs(treeNode.right);
        //计算当前节点的总硬币数
        int coins=left[0]+right[0]+treeNode.val;
       //计算当前节点的总节点数
        int nodes=left[1]+right[1]+1;
        //计算当前节点要移动多少个硬币给父节点或者从父节点拿入硬币
        ans+=Math.abs(coins-nodes);
        return new int[]{coins,nodes};
    }
}

复杂度分析

时间复杂度:O(n),n为二叉树的节点个数。
空间复杂度:O(h)。h为二叉树的高度。文章来源地址https://www.toymoban.com/news/detail-561611.html

运行结果

979. 在二叉树中分配硬币(力扣),leetcode题目,leetcode,算法,职场和发展

优化代码

思路

在函数dfs(node)中,我们首先遍历左右子树,获得左右子树的是有多余的还不足的硬币数量left和right。那么答案ans需要加上|left| + |right|表示左右子树硬币移动的次数,也就是说左右子树中的金币移动到他们的父节点次数。然后,返回当前节点也就是左右子树的父节点所形成的整个子树的硬币是多余的量还是不足的量,也就是加上左右子树的多余的量还是不足的量再加上当前节点硬币的数量减去减去自己一个节点数。left +right+node.val - 1。直到根节点。

测试代码

class Solution{
    private  int ans=0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode treeNode){
        if (treeNode==null)return 0;

        int left=dfs(treeNode.left);
        int right=dfs(treeNode.right);

        ans+=Math.abs(left)+Math.abs(right);

        return left+right+treeNode.val-1;
    }
}

运行结果

979. 在二叉树中分配硬币(力扣),leetcode题目,leetcode,算法,职场和发展

复杂度分析

时间复杂度:O(n),n为二叉树的节点个数。
空间复杂度:O(h)。h为二叉树的高度。

到了这里,关于979. 在二叉树中分配硬币(力扣)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++力扣题目617--合并二叉树

    给你两棵二叉树:  root1  和  root2  。 想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则

    2024年01月20日
    浏览(41)
  • C++力扣题目101--对称二叉树

    力扣题目链接(opens new window) 给定一个二叉树,检查它是否是镜像对称的。   首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了 其实我们要比较

    2024年01月25日
    浏览(38)
  • C++力扣题目104--二叉树的最大深度

    给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 返回它的最大深度 3 。 看完本篇可以一起做了如下两道题目: 104.二叉树的最大深度(opens n

    2024年01月16日
    浏览(63)
  • C++力扣题目--94,144,145二叉树非递归(迭代)遍历

    为什么可以用迭代法(非递归的方式)来实现二叉树的前后中序遍历呢? 我们在栈与队列:匹配问题都是栈的强项 (opens new window)中提到了, 递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中 ,然后递归返回的时候,从栈顶弹出上

    2024年02月02日
    浏览(36)
  • LeetCode(力扣)236. 二叉树的最近公共祖先Python

    https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

    2024年02月10日
    浏览(36)
  • 【LeetCode】(力扣) c/c++刷题-145. 二叉树的后序遍历

    来源:力扣(LeetCode) 链接: 力扣  

    2024年02月01日
    浏览(63)
  • 【LeetCode力扣】297. 二叉树的序列化与反序列化

      目录 1、题目介绍 2、解题思路  2.1、详细过程图解 2.2、代码描述   2.3、完整代码   原题链接:297. 二叉树的序列化与反序列化 - 力扣(LeetCode)   示例 1: 输入: root = [1,2,3,null,null,4,5] 输出: [1,2,3,null,null,4,5] 示例 2: 输入: root = [ ] 输出: [ ] 示例 3: 输入: root = [1

    2024年02月08日
    浏览(64)
  • 算法通关村——二分查找在二叉树中的应用

    二叉搜索树中的搜索 给定二叉搜索树(BST)的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。 一开始以为很难,无从下手,但是题目已经规定了这是二叉搜索树,意味着将元素按照中序排

    2024年02月13日
    浏览(36)
  • 【刷题笔记8.11】LeetCode题目:二叉树中序遍历、前序遍历、后序遍历

    (一)题目描述 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 (二)分析 二叉树中序遍历,遍历顺序:左节点 -》 根节点 -》 右节点 ( 注意:二叉树的前、中、后序遍历就是以根为基准,前序遍历根在最前面,中序遍历根在中间,后序遍历根在最后面 ) (三)

    2024年02月13日
    浏览(37)
  • 设计一个求结点x在二叉树中的双亲结点算法

    要设计一个求二叉树中指定节点 x 的双亲节点的算法,可以按照以下步骤进行: 创建一个递归函数  findParent(root, x) ,其中  root  是当前子树的根节点, x  是要查找其双亲节点的节点。 首先检查根节点是否为空或者根节点是否就是要查找的节点 x,若是,则说明 x 没有双亲

    2024年02月04日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包