当前位置: 首页 > news >正文

【题解】二叉树中和为某一值的路径(一)

二叉树中和为某一值的路径(一)

题目链接:二叉树中和为某一值的路径(一)

解题思路1:递归

我们或许想记录下每一条从根节点到叶子节点的路径,计算出该条路径的和,但此种思路用递归稍麻烦,我们可以试着把和转换为差,从根节点开始,sum就减去根节点的值,如果到叶子节点,减为0了,那就证明此路径满足要求

递归结束条件:节点为空,意味着已经走过了叶子节点,返回;每当检查到某节点没有子节点,则说明该节点为叶子节点,如果此时sum的值减去该节点的值刚好为0,则说明找到了路径

返回值:将子问题中是否有复合新目标值的路径层层往上返回

本级任务:每一层需要检查是否到了叶子节点,如果没有则递归进入子节点,同时更新sum值减掉本层的节点值

代码如下:

    bool hasPathSum(TreeNode* root, int sum) {if(root == nullptr) return false;if(root->left==nullptr && root->right==nullptr && sum-root->val==0) return true;return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);}

解题思路2:非递归,栈+DFS

我们上面是一步一步减去当前root的值,看最后root为空时,sum的值是否为0,采用递归实现,在此,我们采用走一步加上一步当前节点的值,看最后加和是否满足sum,我们采用栈和深度优先搜索来实现

深度优先搜索:深度优先搜索一般用于树或者图的遍历,其他有分支也适用,它是从初始点开始,一直沿着同一个分支遍历,直到该分支结束,然后回溯到上一级继续沿着一个分支走到底,如此往复,直到所有的节点都有被访问到

具体步骤:

首先检查空节点,若为空树,则返回

使用栈嵌套pair,first记录节点,second记录经过的节点的值的和。根节点及根节点的值先进栈。

遍历的时候判断是否是叶子节点,且和是否等于sum,是则返回true

如果节点有子节点,就入栈,并更新路径和

如果遍历结束也没有找到规定的路径,则返回false,该二叉树中没有符合条件的路径

当到达当前节点时,second中的值已经加过该节点的值了

代码如下:

    bool hasPathSum(TreeNode* root, int sum) {if (root == nullptr) return false;//栈辅助深度优先遍历,并记录到相应节点的路径和stack<pair<TreeNode*, int>> s;//根节点先入栈s.push({root, root->val});while (!s.empty()) {auto temp = s.top();s.pop();//是叶子节点,且路径和等于sumif (temp.first->left == nullptr && temp.first->right == nullptr &&temp.second == sum)return true;//左节点入栈if (temp.first->left != nullptr)s.push({temp.first->left, temp.first->left->val + temp.second});//右节点入栈if (temp.first->right != nullptr)s.push({temp.first->right, temp.first->right->val + temp.second});}return false;}
http://www.lryc.cn/news/129452.html

相关文章:

  • css中变量和使用变量和运算
  • 数据结构之线性表的类型运用Linear Lists: 数组,栈,队列,链表
  • 成瘾机制中微生物群的神秘角色
  • arm安装docker与docker-copose
  • 9.文件基本操作
  • 【Java】Spring——Bean对象的作用域和生命周期
  • 数字孪生助力智慧水务:科技创新赋能水资源保护
  • css 实现文字横向循环滚动
  • VuePress 数学公式支持
  • stm32控制蜂鸣器源代码(附带proteus线路图)
  • selinux
  • 使用opencv4.7.0部署yolov5
  • Python - 协程基本使用详解【demo】
  • Android MVVM架构模式,详详详细学习
  • 亿赛通电子文档安全管理系统 RCE漏洞复现
  • 星际争霸之小霸王之小蜜蜂(三)--重构模块
  • JS的解析与Js2Py使用
  • Spring Bean的生命周期总结(包含面试题)
  • SpringjDBCTemplate_spring25
  • 设计模式——桥接模式
  • 改进YOLO系列:2.添加ShuffleAttention注意力机制
  • 利用Opencv实现人像迁移
  • Lnton羚通算法算力云平台在环境配置时 OpenCV 无法显示图像是什么原因?
  • 【JavaEE进阶】MyBatis的创建及使用
  • 职业学院物联网实训室建设方案
  • 3 个 ChatGPT 插件您需要立即下载3 ChatGPT Extensions You need to Download Immediately
  • 屏蔽socket 实例化时,握手阶段报错信息WebSocket connection to ‘***‘ failed
  • 单发多框检测(SSD)【动手学深度学习】
  • “RFID与光伏板的完美融合:探索能源科技的新时代!“
  • 算法leetcode|71. 简化路径(rust重拳出击)