404 - 左叶子之和(sum-of-left-leaves)

Create by jsliang on 2019-7-25 08:17:01
Recently revised in 2019-7-25 08:53:31

一 目录

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

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

二 前言

返回目录

计算给定二叉树的所有左叶子之和。

示例:

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24。

三 解题

返回目录

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

  • 解题代码
const sumOfLeftLeaves = (root) => {
  let sum = 0;
  const ergodic = (root) => {
    if (!root) {
      return;
    }
    if (root.left && !root.left.left && !root.left.right) {
      sum += root.left.val;
    }
    return ergodic(root.right) + ergodic(root.left);
  }
  ergodic(root);
  return sum;
};

四 执行测试

返回目录

  • root
const root = {
  val: 3,
  left: { val: 9, left: null, right: null },
  right: {
    val: 20,
    left: { val: 15, left: null, right: null },
    right: { val: 7, left: null, right: null },
  },
};
  • return
24

五 LeetCode Submit

返回目录

√ Accepted
  √ 102/102 cases passed (84 ms)
  √ Your runtime beats 70.87 % of javascript submissions
  √ Your memory usage beats 91.67 % of javascript submissions (33.9 MB)

六 解题思路

返回目录

首先,咱再写一次树的遍历套路:

const ergodic = function(root) {
  if (!root) {
    return '!#';
  }
  return '!' + root.val + ergodic(root.left) + ergodic(root.right);
}

然后,咱尝试一下破解:

const sumOfLeftLeaves = (root) => {
  let sum = 0;
  const ergodic = (root) => {
    if (!root) {
      return;
    }
    if (root.left) {
      sum += root.left.val;
    }
    return ergodic(root.right) + ergodic(root.left);
  }
  ergodic(root);
  return sum;
};

Submit 提交后提示:

× Wrong Answer
  × 31/102 cases passed (N/A)
  × testcase: '[1,2,3,4,5]'
  × answer: 6
  × expected_answer: 4
  × stdout:

它的意思是:我们只要叶子的和,不是需要所有左节点的和

所以,在下面这种结构中,我们的代码就错了。

const root = {
  val: 1,
  left: {
    val: 2,
    left: { val: 4, left: null, right: null },
    right: { val: 5, left: null, right: null },
  },
  right: { val: 3, left: null, right: null },
};

OK,那么我们优化下代码再提交尝试:

const sumOfLeftLeaves = (root) => {
  let sum = 0;
  const ergodic = (root) => {
    if (!root) {
      return;
    }
    if (root.left && !root.left.left && !root.left.right) {
      sum += root.left.val;
    }
    return ergodic(root.right) + ergodic(root.left);
  }
  ergodic(root);
  return sum;
};

Submit 提交结果:

√ Accepted
  √ 102/102 cases passed (84 ms)
  √ Your runtime beats 70.87 % of javascript submissions
  √ Your memory usage beats 91.67 % of javascript submissions (33.9 MB)

最后,我们尝试优化下代码:

const sumOfLeftLeaves = (root, left) => {
  if (!root) {
    return 0;
  }
  if (!root.left && !root.right && left) {
    return root.val;
  }
  return sumOfLeftLeaves(root.left, true) + sumOfLeftLeaves(root.right);
};

七 进一步思考

返回目录

虽然我们使用递归遍历树屡试不爽。但是,如果我们能尝试更多方法,例如迭代,相信我们能逐渐丰富我们的思维模式,从而在面对问题的时候能尝试各种不同的方法求解。


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

图

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-07-25 10:11:12

results matching ""

    No results matching ""