DFS | 从根到叶的二进制数之和【附递归展开图】

这篇具有很好参考价值的文章主要介绍了DFS | 从根到叶的二进制数之和【附递归展开图】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

DFS | 从根到叶的二进制数之和【附递归展开图】
👉 力扣原题链接

一、思路分析

首先我们来分析一下本题的思路

  • 题目说到要求解每一条路径上的结点数字之和,但是本题并不是就简单的累加,而是要结合二进制的知识
  • 对于每一条从根到叶的路径都代表一个从最高有效位开始的二进制数,要注意的是这个最高有效位,也就是说越往下走权重越小

DFS | 从根到叶的二进制数之和【附递归展开图】

  • 首先题目要求要我们求累加和,那么最简单的一个思路就是一个变量res去累加所有的数字之和,但是呢并不是每个结点的路径和都是一样的,所以我们还需要一个变量preSum求出从根结点到当前结点的和
  • 因为根节点的权重来得最大,但是我们并不知道这棵树的深度为多少,也就无法确定根节点的权重是否为多少,所以我们要通过【DFS】去遍历这棵树,直到每次碰到叶子结点为止才可以确定从根结点到当前结点的长度,才能得出每一个结点的权重

DFS | 从根到叶的二进制数之和【附递归展开图】

二、代码详解

有了思路,接下去我们来看看代码该如何书写

根据递归三部曲:

  1. 确定递归函数的参数和返回值
  • 本题的累加和res我将其定义为成员变量,DFS单独定义为一个成员函数,所以不需要考虑返回值,只要将将根节点传入即可,但是我们还要计算每条路径的和,所以每一层的递归还需一个preSum
  1. 确定终止条件
  • 对于终止条件,这个很直观,因为一直往下递归,碰到叶子结点就终止回调,所以判断root == NULL即可
  1. 确定单层递归的逻辑
  • 最后就是单层递归的逻辑,每遍历到一个结点时,我们都需要将当前结点值和从根结点到当前结点的所累加的和preSum进行一个相加,但是又要考虑到二进制权重的问题:
  • 因为每一个结点的值均为0或者是1,所以根据二进制上每一位的关系,高一位的权重都比低一位的权重大2倍,所以我们每次在进入当前递归层的时候,都会获取到上一层计算出来的preSum,只需要将其乘2,就可以使上一层的根成为当前层的高一位权重,当然,你也可以使用位运算<< 1
  • 若是当前层的根并不是叶子结点的话,就继续递归其左孩子和右孩子,若为叶子结点的话,表示一条路径递归完毕,更新res加上累加后的preSum

以下是整体代码展示💻

 */
class Solution {
private:
    int res = 0;        //累加和作为成员函数
public:
    void DFS(TreeNode* root, int preSum)
    {
        if(!root)   return;
        preSum = preSum * 2 + root->val;        //用于单条路径累加和

        if(!root->left && !root->right)
        {
            res += preSum;      //若是碰到叶子结点了,就累加次路径的结点和
        }

        //递归当前根结点的左右子树
        DFS(root->left, preSum);
        DFS(root->right, preSum);
    }
    int sumRootToLeaf(TreeNode* root) {
        DFS(root, 0);
        return res;
    }
};

三、算法图解

对于上面的递归部分,我画了【递归展开图】,可以帮助理解,你也可以试着自己画画看😀

DFS | 从根到叶的二进制数之和【附递归展开图】

以上就是这题力扣1022.从根到叶的二进制数之和相关题解,感谢您的阅读🌹

DFS | 从根到叶的二进制数之和【附递归展开图】文章来源地址https://www.toymoban.com/news/detail-403071.html

到了这里,关于DFS | 从根到叶的二进制数之和【附递归展开图】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 每日OJ题_二叉树dfs②_力扣129. 求根节点到叶节点数字之和

    目录 力扣129. 求根节点到叶节点数字之和 解析代码 129. 求根节点到叶节点数字之和 难度 中等 给你一个二叉树的根节点  root  ,树中每个节点都存放有一个  0  到  9  之间的数字。 每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶节点的路径  1 - 2 - 3

    2024年02月21日
    浏览(43)
  • 【十进制 转 二进制】【二进制 转 十进制】10进制 VS 2进制【清华大学考研机试题】

    原题链接 本题我们先需要知道 十进制 如何转 二进制 二进制 如何转 十进制 十进制 如何转 二进制: 十进制转成二进制 例如 173 转成 二进制 就把173 短除法 除到0 然后 得到的余数, 从下往上写 二进制 转成 十进制 利用如图方法,把二进制 转成 十进制 本题是高精度,如何

    2023年04月26日
    浏览(46)
  • 将数据转二进制流文件,用PostMan发送二进制流请求

    一、将byte数组转二进制流文件,并保存到本地 byte [] oneshotBytes=new byte[]{78,-29,51,-125,86,-105,56,82,-94,-115,-22,-105,0,-45,-48,-114,27,13,38,45,-24,-15,-13,46,88,-90,-66,-29,52,-23,40,-2,116,2,-115,17,36,15,-84,88,-72,22,-86,41,-90,-19,-58,19,99,-4,-63,29,51,-69,117,-120,121,3,-103,-75,44,64,-58,-34,73,-22,110,-90,92,-35,-18,-128,16,-

    2024年02月15日
    浏览(42)
  • java图片转二进制流_java将文件转化成二进制流

    二进制流的主要编码格式是base64码。可以在网上找一些在线转base64编码的网站进行尝试转换。 例如:http://imgbase64.duoshitong.com/然后通过前端展现和下载。 前端显示二进制流图片(src中放置base64码及二进制流) 前端下载二进制流文件(herf中放置base64码及二进制流,download后面放

    2024年02月06日
    浏览(56)
  • 后端返回二进制流,前端处理二进制文件流,实现预览图片以及PDF

    1、首先预览PDF需要 后端 将响应头 Content-Type 设置为PDF类型 application/pdf ,不能预览,会直接下载 2、 前端 定义接口:并设置相应类型 responseType 为 blob 请求数据:通过 window.URL.createObjectURL(res) 转成本地预览地址, 在通过 window.open() 方法打开转成本地预览地址即可预览PDF,如下

    2024年02月15日
    浏览(55)
  • Python中二进制十进制转换

            hello大家好,今天我想和大家分享一下在Python中进制转换加减法的方法。         比如现在我们需要求100 + 10,然后需要将结果110以二进制的形式返回,又或者我们现在有一个小需求,就是要计算二进制1010和二进制1011的和是多少,然后依旧以二进制的形式返回

    2024年02月16日
    浏览(58)
  • 【Python 千题 —— 基础篇】进制转换:十进制转二进制

    题目描述 计算机底层原理中常使用二进制来表示相关机器码,学会将十进制数转换成二进制数是一个非常重要的技能。现在编写一个程序,输入一个十进制数,将其转换成二进制数。 输入描述 输入一个十进制数。 输出描述 程序将输入的十进制数转换为二进制数,并输出其

    2024年02月07日
    浏览(79)
  • C语言【进制转换】35:输出二进制补码

    总时间限制:  1000ms 内存限制:  65536kB 描述 输入一个整型(int)的整数,输出它的32位二进制补码。 输入 一个整型整数。 输出 输出一行,即该整数的补码表示。 样例输入 样例输出 00000000000000000000000000000111 代码实现: 首先要明白 (按位与)和 (左移)的用法 规则: 11=1 10=

    2024年02月07日
    浏览(68)
  • python十进制转二进制方法详解

      在 Python中,十进制数可以转换成二进制数。例如: 但是,十进制数不是直接转换成二进制,而是先转换成二进制数,再转换成十进制。接下来我们来看看具体的实现方法: 首先我们来看一个例子: 上面代码中,使用了循环遍历的方法。从这个例子中我们可以发现,需要遍

    2023年04月19日
    浏览(101)
  • 【FPGA仿真】Matlab生成二进制、十六进制的txt数据以及Vivado读取二进制、十六进制数据并将结果以txt格式保存

    在使用Vivado软件进行Verilog程序仿真时可能需要对模块输入仿真的数据,因此我们需要一个产生数据的方法(二进制或者十六进制的数据),Matlab软件是一个很好的工具,当然你也可以使用VS等工具。 以下分别给出了使用Matlab模拟产生二进制和十六进制数据的例子,例子仅供参

    2024年02月01日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包