路径总和
路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。
示例
给定如下二叉树，以及目标和sum = 22，返回true，因为存在目标和为22的根节点到叶子节点的路径5->4->11->2。
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1题解
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
return dfs(root, sum, 0);
};
function dfs(root, sum, tmp){
if(!root) return false;
tmp = tmp + root.val;
if(!root.left && !root.right) return tmp === sum ;
return dfs(root.left, sum, tmp) || dfs(root.right, sum, tmp);
}思路
深度优先遍历即可，首先处理边界条件，如果节点为null则直接返回false，之后将tmp值与节点值相加，如果此节点为根节点，那么就返回tmp是否与sum相等的判断，最后进行深度递归遍历，利用短路运算效应，在左子树为true的情况下不会再进行右子树的递归运算，在右子树为true的情况下会直接返回上层递归运算，这样即可实现路径总和的计算。
每日一题
https://github.com/WindrunnerMax/EveryDay题源
https://leetcode-cn.com/problems/path-sum本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录