经典笔试题: 二叉树中和为某一值的路径(路径总和)
微信搜一搜:
bigsai
大家都在关注的刷题、学习数据结构和算法宝藏项目
关注回复进群即可加入力扣打卡群,欢迎划水。
这两题是相似问题,循序渐进。也是力扣和剑指offer的经典题。
路径总和
题目描述(题目链接)
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ,判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 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
示例 3:
输入:root = [1,2], targetSum = 0
输出:false
提示:
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
分析
对于这种判断的,只要有一个满足条件的即可,在遍历路径上肯定使用dfs遍历。向下一层的时候就处理一下当前层的值,这样有一个满足的结果那么就可以返回true。当然,这里我就没有剪枝,如果有正确结果的话也可停止递归判断。
具体实现的代码为:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null)
return false;
int value=targetSum-root.val;
if(root.left==null&&root.right==null)
{
if(value==0)
return true;
}
else {
return hasPathSum(root.left,value)||hasPathSum(root.right, value);
}
return false;
}
}
路径总和Ⅱ
题目描述(题目链接)
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
分析:
这个问题就是要求返回所有满足要求的结果,和上题略有不同就是需要找到所有结果并且保存,保存结果的话我们就需要一个List<Integer>
存储遍历的结果,而List<List<Integer>>
用来存储所有的结果,所以在递归回溯的过程中就需要借助回溯的过程经过每一个状态,满足状态的就将这个List复制到结果集中去,需要返回的时候还需要移除当前层加入的结果。
具体实现的代码为:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> team = new ArrayList<Integer>();
List<List<Integer>> value = new ArrayList<List<Integer>>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null)
return value;
team.add(root.val);
targetSum-=root.val;
if(targetSum==0&&root.left==null&&root.right==null)
{
value.add(new ArrayList<Integer>(team));
}
pathSum(root.left, targetSum);
pathSum(root.right, targetSum);
team.remove(team.size()-1);
return value;
}
}
原创不易,bigsai请你帮两件事帮忙一下:
-
star支持一下, 您的肯定是我在平台创作的源源动力。
-
微信搜索「bigsai」,关注我的公众号,不仅免费送你电子书,我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见!
本文同步分享在 博客“Big sai”(CSDN)。
如有侵权,请联系 [email protected] 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。
- 结合大学四年经验,带你揭秘高效自学Java的方法和路线(从认识、方法、反馈3个角度出发)
- 因为LRU设计效率太低被pass了
- 动态规划,就这些最常见了!
- 刷题难,程序员如何玩转力扣?
- 如何搞定力扣刷题?
- 什么是字典树
- 数据结构与算法—栈详解
- 520,花一夜给女神写走迷宫游戏
- 双链表最详细图解
- 大数加减乘除,一文搞定!
- (阿里高频笔试)大数加减乘除,一文彻底搞定
- 【手写数据结构】双链表最详细图解
- 经典笔试题: 二叉树中和为某一值的路径(路径总和)
- 数据结构与算法必知基础知识
- 一文搞懂线性表(顺序表、链表)
- LeetCode 90子集Ⅱ&91解码方法
- 跳表(SkipList)|会跳的链表真的非常diao
- 三本逆袭成为学霸硕士研究生
- 5张图搞懂Java引用拷贝、浅拷贝、深拷贝
- 花五分钟看这篇之前,你才发现你不懂RESTful