112 - 路径总和(path-sum)

Create by jsliang on 2019-6-26 07:43:40
Recently revised in 2019-6-26 09:09:08

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
四 执行测试
五 LeetCode Submit
六 解题思路
七 进一步思考

二 前言

返回目录

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

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

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

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码
var hasPathSum = function(root, sum) {
  if (!root) {
    return false;
  }
  sum -= root.val;
  if (!root.left && !root.right) {
    return sum === 0;
  }
  return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
};

四 执行测试

返回目录

  • sum18
  • root
//       5
//      / \
//     4   8
//    /   / \
//   11  13  4
//  /  \      \
// 7    2      1
const root = {
  val: 5,
  left: {
    val: 4,
    left: {
      val: 11,
      left: { val: 7, left: null, right: null },
      right: { val: 2, left: null, right: null },
    },
    right: null,
  },
  right: {
    val: 8,
    left: { val: 13, left: null, right: null },
    right: {
      val: 4,
      left: null,
      right: { val: 1, left: null, right: null },
    }
  }
}
  • return
true

五 LeetCode Submit

返回目录

√ Accepted
  √ 114/114 cases passed (96 ms)
  √ Your runtime beats 91.36 % of javascript submissions
  √ Your memory usage beats 24.14 % of javascript submissions (37.3 MB)

六 解题思路

返回目录

首先,我们尝试打印下递归路线:

// root:
//       5
//      / \
//     4   8
//    /   / \
//   11  13  4
//  /  \      \
// 7    2      1
// 
// sum:18
var hasPathSum = function(root, sum) {
  if (!root) {
    return false;
  }
  sum -= root.val;
  console.log('------');
  console.log(root);
  console.log(sum);
  if (!root.left && !root.right) {
    return sum === 0;
  }
  return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
};

然后,其结果为:

------
{ val: 5,
  left:
   { val: 4,
     left: { val: 11, left: [Object], right: [Object] },
     right: null },
  right:
   { val: 8,
     left: { val: 13, left: null, right: null },
     right: { val: 4, left: null, right: [Object] } } }
13
------
{ val: 4,
  left:
   { val: 11,
     left: { val: 7, left: null, right: null },
     right: { val: 2, left: null, right: null } },
  right: null }
9
------
{ val: 11,
  left: { val: 7, left: null, right: null },
  right: { val: 2, left: null, right: null } }
-2
------
{ val: 7, left: null, right: null }
-9
------
{ val: 2, left: null, right: null }
-4
------
{ val: 8,
  left: { val: 13, left: null, right: null },
  right:
   { val: 4,
     left: null,
     right: { val: 1, left: null, right: null } } }
5
------
{ val: 13, left: null, right: null }
-8
------
{ val: 4,
  left: null,
  right: { val: 1, left: null, right: null } }
1
------
{ val: 1, left: null, right: null }
0

最后,看到这里,小伙伴就清楚了,这道题的解题思路!

七 进一步思考

返回目录

有时候,很多小伙伴会说:哇,jsliang 又破解了一题,然而我看到题目就头痛!

其实,jsliang 有时候也感到烦恼,因为有些题目,非得看题解。

就好比目前这题,一开始我的思路跟题解是反过来的:

//       5
//      / \
//     4   8
//    /   / \
//   11  13  4
//  /  \      \
// 7    2      1
const sum = 22
const root = {
  val: 5,
  left: {
    val: 4,
    left: {
      val: 11,
      left: { val: 7, left: null, right: null },
      right: { val: 2, left: null, right: null },
    },
    right: null,
  },
  right: {
    val: 8,
    left: { val: 13, left: null, right: null },
    right: {
      val: 4,
      left: null,
      right: { val: 1, left: null, right: null },
    }
  }
}

var hasPathSum = function(root, sum) {
  if (!root) {
    return false;
  }
  let index = 0;
  let arr = [];
  let ergodic = function(root) {
    console.log('------');
    console.log(root);
    console.log(arr);
    if (!root) {
      return 0;
    }
    if (!arr[index]) {
      arr[index] = 0;
    }
    arr[index] += root.val;
    if (!root.left && !root.right) {
      // 找到叶子节点,开始逆推
      index += 1;
      return arr[index];
    }
    return ergodic(root.left) + ergodic(root.right);
  }
  ergodic(root);
};

hasPathSum(root, sum);

结果打印:

------
{ val: 5,
  left:
   { val: 4,
     left: { val: 11, left: [Object], right: [Object] },
     right: null },
  right:
   { val: 8,
     left: { val: 13, left: null, right: null },
     right: { val: 4, left: null, right: [Object] } } }
[]
------
{ val: 4,
  left:
   { val: 11,
     left: { val: 7, left: null, right: null },
     right: { val: 2, left: null, right: null } },
  right: null }
[ 5 ]
------
{ val: 11,
  left: { val: 7, left: null, right: null },
  right: { val: 2, left: null, right: null } }
[ 9 ]
------
{ val: 7, left: null, right: null }
[ 20 ]
------
{ val: 2, left: null, right: null }
[ 27 ]
------
null
[ 27, 2 ]
------
{ val: 8,
  left: { val: 13, left: null, right: null },
  right:
   { val: 4,
     left: null,
     right: { val: 1, left: null, right: null } } }
[ 27, 2 ]
------
{ val: 13, left: null, right: null }
[ 27, 2, 8 ]
------
{ val: 4,
  left: null,
  right: { val: 1, left: null, right: null } }
[ 27, 2, 21 ]
------
null
[ 27, 2, 21, 4 ]
------
{ val: 1, left: null, right: null }
[ 27, 2, 21, 4 ]

是的,这份遍历节点的,不完善,我想统计每个分支的和,但它遍历了一遍所有节点,却没做到统计和。

这时候,就涉及到知识盲区了,我知道有 4 条分支,但是如何将 4 条分支统计起来呢?为什么我可以求到所有节点的和,以及知道有 4 条分支,却不能统计 4 条分支的和呢?

抱着这种好奇心,我翻开了题解……


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-06-27 10:04:43

results matching ""

    No results matching ""