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

二叉树路径总和第一题

1题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
示例 2:

输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3:

输入:root = [], targetSum = 0
输出:false
解释:由于树是空的,所以不存在根节点到叶子节点的路径。

2链接

题目链接:112. 路径总和 - 力扣(LeetCode)

视频链接:拿不准的遍历顺序,搞不清的回溯过程,我太难了! | LeetCode:112. 路径总和_哔哩哔哩_bilibili

3解题思路

本题适合递归法,可以使用深度优先遍历的方式(本题前中后序都可以,无所谓,因为中节点也没有处理逻辑)来遍历二叉树

1、确定递归函数的参数和返回类型

参数:需要二叉树的根节点,还需要一个计数器,这个计数器用来计算二叉树的一条边之和是否正好是目标和,计数器为int型。

再来看返回值,递归函数什么时候需要返回值?什么时候不需要返回值?这里卡哥总结如下三点:

a. 如果需要搜索整棵二叉树且不用处理递归返回值,递归函数就不要返回值。

b. 如果需要搜索整棵二叉树且需要处理递归返回值,递归函数就需要返回值。 

c. 如果要搜索其中一条符合条件的路径,那么递归一定需要返回值,因为遇到符合条件的路径了就要及时返回。

而本题我们要找一条符合条件的路径,所以递归函数需要返回值,及时返回,那么返回类型是什么呢?

如图所示:

图中可以看出,遍历的路线,并不要遍历整棵树,所以递归函数需要返回值,可以用bool类型表示。 

2、确定终止条件

计数器如何统计这一条路径的和?

不要去累加然后判断是否等于目标和,那么代码比较麻烦,可以用递减,让计数器count初始为目标和,然后每次减去遍历路径节点上的数值。

如果最后count == 0,同时到了叶子节点的话,说明找到了目标和。

如果遍历到了叶子节点,count不为0,就是没找到。

递归终止条件代码如下:

3、确定单层递归的逻辑

因为终止条件是判断叶子节点,所以递归的过程中就不要让空节点进入递归了。

递归函数是有返回值的,如果递归函数返回true,说明找到了合适的路径,应该立刻返回。

4代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*///递归法
class Solution {
public:bool traversal(TreeNode* node, int target) {//遇到叶子结点,且目标值被减为零,说明符合题意,返回True否则falseif (node->left == nullptr && node->right == nullptr && target == 0) return true;if (node->left == nullptr && node->right == nullptr && target != 0) return false;if (node->left) { //左子树target -= node->left->val; //目标值每访问一个节点就减去其值//说明在递归的过程中找到了目标路线,一层层返回上来tureif (traversal(node->left, target)) return true;target += node->left->val;//回溯,目的为了还原目标值,去遍历右子树}if (node->right) {//右子树,下面同理target -= node->right->val;if (traversal(node->right, target)) return true;target += node->right->val;}return false;//以上都没返回true说明没找到,那就返回false}bool hasPathSum(TreeNode* root, int targetSum) {if (root == nullptr) return false;//空节点return(traversal(root, targetSum - root->val));//调用递归函数}
};

一定要看懂上面的二叉树回溯图,和这个代码对应极其密切

http://www.lryc.cn/news/44237.html

相关文章:

  • @RefreshScope源码解析
  • 【开发】后端框架——Spring
  • vue中的自定义指令
  • 技术分享及探讨
  • 人工智能AI
  • 2022天梯赛补题
  • 字节跳动测试岗面试挂在2面,复盘后,我总结了失败原因,决定再战一次...
  • Nodejs实现通用的加密和哈希算法(MD5、SHA1、Hmac、AES、Diffie-Hellman、RSA),crypto模块详解
  • 测试行业3年经验,从大厂裸辞后,面试阿里、字节全都一面挂,被面试官说我的水平还不如应届生
  • 安卓悬浮窗口,  丝滑双指缩放视频窗口
  • 300左右哪款蓝牙耳机适合学生用?四款便宜质量好的蓝牙耳机推荐
  • 桥梁设计模式
  • 【华为OD机试 2023最新 】 新员工座位(C++)
  • 蓝桥杯刷题第二十二天
  • CentOS从gcc 4.8.5 升级到gcc 8.3.1
  • 【人人都能读标准】12. 原始类型的编码形式
  • VUE进行前后端交互
  • ThingsBoard Gateway:物联网设备数据采集与集成的强大解决方案
  • 什么是镜像/raid
  • 【Python】如何有效比较两个时间序列在图形上的相似度?
  • JavaEE-常见的锁策略和synchronized的锁机制
  • 信息化,数字化,智能化是三种不同的概念吗?
  • 【华为OD机试 2023最新 】 匿名信(C++ 100%)
  • 硬件语言Verilog HDL牛客刷题day05 时序逻辑部分
  • Ajax 入门
  • 半导体器件基础06:发光二极管
  • AutoCV第二课:Python基础
  • LeetCode算法 打家劫舍 和 打家劫舍II C++
  • 蓝桥杯刷题冲刺 | 倒计时10天
  • 个人练习-Leetcode-剑指 Offer II 109. 开密码锁