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

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.

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:

▉ 问题分析

2）第一个想法就是一个个进行相加，将每条路径相加完成之后，判断是否达到当前目标值？
3）但是 （2）的解决方案的想法要用到递归上，需要转变一下思路，毕竟我们要用递归的编程技巧来解决，所以思维需要稍微转变一下（将问题化成子问题，子问题与总问题有相同的解决思路）。

▉ 算法思路

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...

欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。