[路飞]_leetcode-979-在二叉树中分配硬币

简介: leetcode-979-在二叉树中分配硬币

网络异常,图片无法展示
|


「这是我参与2022首次更文挑战的第29天,活动详情查看:2022首次更文挑战


[题目地址][B站地址]


给定一个有 N 个结点的二叉树的根结点 root,树中的每个结点上都对应有 node.val 枚硬币,并且总共有 N 枚硬币。


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


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


示例 1:


网络异常,图片无法展示
|


输入: [3,0,0]
输出: 2
解释: 从树的根结点开始,我们将一枚硬币移到它的左子结点上,一枚硬币移到它的右子结点上。
复制代码


示例 2:


网络异常,图片无法展示
|


输入: [0,3,0]
输出: 3
解释: 从根结点的左子结点开始,我们将两枚硬币移到根结点上 [移动两次]。然后,我们把一枚硬币从根结点移到右子结点上。
复制代码


示例 3:


网络异常,图片无法展示
|


输入: [1,0,2]
输出: 2
复制代码


示例 4:


网络异常,图片无法展示
|


输入: [1,0,0,null,3]
输出: 4
复制代码


提示:


  1. 1<= N <= 100
  2. 0 <= node.val <= N


解题思路


首先,我们可以将本题所求的移动次数拆分为每个结点上所需的移动次数。


接下来的问题就是如何求每个结点上所需的移动次数?


因为本题要求每个结点上只有一枚硬币,如果当前结点是叶子结点:


  1. 如果该结点没有硬币,则需要移动过来一枚硬币
  2. 如果该结点的硬币数量大于 1,则需要移走 node.val-1 枚硬币


上面的移动硬币数量也就是该结点位置所需的移动次数。


那如果当前结点不是叶子结点呢?


这个时候就需要知道其左右子树的情况


  1. 如果左右子树的硬币数量是有多余的,则会给到当前结点一定数量的硬币,如果该硬币数量加上当前节点的 node.val 大于 1,则当前结点需要将多余的硬币继续向上移动
  2. 如果左右子树的硬币数量是不够的,则需要向当前结点索取一定数量的硬币,如果当前结点没有,则需要向它的父结点索取


这里我们假设左右子树返回的数量为 l,r,如果值为 0,则说明该子树不需要索取硬币,也没有多余硬币,如果为正数,则说明该子树硬币有多余,如果为负数,则说明该子树硬币不够。


基于以上条件,当前节点向上返回的值应该是 l+r+node.val-1,而当前节点所需的移动次数是 l+r+node.val-1 的绝对值,因为不管是索取还是向上给予,都需要对应的移动次数。


基于以上分析,很明显本题需要递归处理二叉树中的每一个结点,并在回溯的过程中基于子树返回的信息确定当前结点的操作次数,所以我们需要采用前序遍历处理二叉树。


代码实现


var distributeCoins = function (root) {
  // 初始化结果值为 0
  let res = 0
  // 前序遍历二叉树
  function preorder(node) {
    // 如果当前节点为空节点,不需要操作次数,返回 0
    if (node === null) return 0
    // 获取左右子树返回的值,对应其多余或需要的硬币数量
    const l = preorder(node.left),
      r = preorder(node.right),
    // 计算当前结点多余或所需的硬币数量
    step = l + r + node.val - 1;
    // 记录操作次数
    res += Math.abs(step)
    // 返回当前节点值
    return step
  }
  // 调用前序遍历处理二叉树
  preorder(root)
  // 返回结果值
  return res
}
复制代码


至此我们就完成了 leetcode-979-在二叉树中分配硬币


如有任何问题或建议,欢迎留言讨论!👏🏻👏🏻👏🏻

目录
打赏
0
0
0
0
5
分享
相关文章
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
193 14
|
3月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
77 4
|
3月前
|
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
82 10
|
3月前
|
【LeetCode 热题100】【二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST】(详细解析)(Go语言版)
本文详细解析了二叉树构造的两类经典问题:通过前序与中序遍历重建二叉树(LeetCode 105),以及将有序数组转化为平衡二叉搜索树(BST,LeetCode 108)。文章从核心思路、递归解法到实现细节逐一拆解,强调通过索引控制子树范围以优化性能,并对比两题的不同构造逻辑。最后总结通用构造套路,提供进阶思考方向,帮助彻底掌握二叉树构造类题目。
184 9
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
184 10
|
9月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
68 0
|
9月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
52 0
|
9月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
68 0
|
9月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
68 0
|
9月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
62 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问