四川省建设厅申报网站,南宁模板建站,wordpress jnews,学校网站管理系统1题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
叶子节点 是指没有…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
视频链接拿不准的遍历顺序搞不清的回溯过程我太难了 | LeetCode112. 路径总和_哔哩哔哩_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));//调用递归函数}
};
一定要看懂上面的二叉树回溯图和这个代码对应极其密切
