LeetCode 之 JavaScript 解答第112题 —— 路径总和（Path Sum）

lylwyy2016 发布于2019-08-26 13:44 / 1072人阅读

摘要：小鹿题目路径总和给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明叶子节点是指没有子节点的节点。

Time：2019/4/26
Title: Path Sum
Difficulty: Easy
Author: 小鹿

题目：Path Sum（路径总和）

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

Example:

Given the below binary tree and sum = 22,

      5
     / 
    4   8
   /   / 
  11  13  4
 /        
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solve:

▉ 问题分析

1）搜索从根节点到叶子节点能够达到目标值，毋庸置疑，一看到检索二叉搜索树，就应该想起递归。

2）第一个想法就是一个个进行相加，将每条路径相加完成之后，判断是否达到当前目标值？

3）但是（2）的解决方案的想法要用到递归上，需要转变一下思路，毕竟我们要用递归的编程技巧来解决，所以思维需要稍微转变一下（将问题化成子问题，子问题与总问题有相同的解决思路）。

▉ 算法思路

1）既然要用到递归来解决，这样来想，每遍历一个结点，我们就用 sum 减去当前结点，然后问题就会变成从当前结点到叶子节点能够满足 sum 减去当前结点的值，那么就存在满足条件的路径。

2）在（1）中，将问题化成子问题，然后子问题和问题有相同的解决思路，那么就可以使用递归来解决。

3）用 flag 做标识，一旦满足路径之和等于目标值，就让改变 flag 的状态。

▉ 代码实现

 var hasPathSum = function(root, sum) {
     let flag = false;
     // 判断当前二叉树是否等于 null
     if(root == null) return false;

     dfs = (root,sum)=>{
         // 如果当前结点为 null ，返回 false
         if(root == null) return false;
         // 判断左右子树是否为 null
         if(root.left == null && root.right == null){
             // 如果不为 null，就判断当前的值和最后一个结点值是否相同
             if(sum == root.val){
                 flag = true;
                 return;
             }
         }
         // 递归搜索所有路径
         dfs(root.left,sum - root.val)
         dfs(root.right,sum - root.val)
     }
     dfs(root,sum)
     return flag;
 };

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...
欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。

GPU云服务器云服务器 javascript算法题汇编语言程序设计第二版课后题答案 javascript必问面试题 javascript权威指南第六版

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109400.html

LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 之 JavaScript 解答第104题 —— 二叉树的最大深度

摘要：小鹿题目二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。求二叉树的深度，必然要用到递归来解决。分别递归左右子树。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿题目：Maximum Depth of Binary Tre...

boredream 2019-08-23 17:07 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 之 JavaScript 解答第142题 —— 环形链表 II（Linked Li

摘要：说明不允许修改给定的链表。算法思路题目要求返回单链表中存在循环链表的位置。首先，先判断该单链表是否存在循环链表用两个快慢指针分别指向链表的头部，每次移动两步，每次移动一步，移动的步数是的两倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿题目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 评论0 收藏0