2
#yyds干货盘点# 面试必刷TOP101：二叉树中和为某一值的路径(一)
source link: https://blog.51cto.com/u_15488507/5608484
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：二叉树中和为某一值的路径(一)
精选 原创1.简述：
描述给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
给出如下的二叉树，，
返回true，因为存在一条路径 的节点值之和为 22
数据范围：
1.树上的节点数满足
2.每 个节点的值都满足
要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度
示例1{5,4,8,1,11,#,9,#,#,2,7},22
{1,2},0
false
{1,2},3
false
2.代码实现：
public class Solution {
/**
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if (root == null) {
return false;
}
// 深度优先遍历
return dfs(root, sum);
}
private boolean dfs(TreeNode curNode, int target) {
// 目标路径不存在，开始回溯
if (curNode == null) {
return false;
}
// 更新目标值
target -= curNode.val;
// 当当前节点为叶子节点并且目标路径存在时，返回 true
if (curNode.left == null && curNode.right == null && target == 0) {
return true;
}
// 对左右分支进行 dfs
return dfs(curNode.left, target) || dfs(curNode.right, target);
}
}
/**
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if (root == null) {
return false;
}
// 深度优先遍历
return dfs(root, sum);
}
private boolean dfs(TreeNode curNode, int target) {
// 目标路径不存在，开始回溯
if (curNode == null) {
return false;
}
// 更新目标值
target -= curNode.val;
// 当当前节点为叶子节点并且目标路径存在时，返回 true
if (curNode.left == null && curNode.right == null && target == 0) {
return true;
}
// 对左右分支进行 dfs
return dfs(curNode.left, target) || dfs(curNode.right, target);
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK