专栏首页前端小书童一天一大 leet(路径总和)难度:简单-Day20200707

一天一大 leet(路径总和)难度:简单-Day20200707

题目:

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

说明

叶子节点是指没有子节点的节点。

示例

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

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

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

抛砖引玉

  • 使用递归遍历二叉树
  • 递归的逻辑:
    • 参数上一个节点的左节点或者右节点,减去上一个节点的和
    • 遇到叶子节点下一个节点终止
    • sum 减去递归中遇到的节点,返回 sum 与最后的节点差值是否为 0
/**
 * 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) {
  // 遍历到叶子节点下一个节点-终止递归
  if (root === null) return false

  // 遍历到叶子节点 判断剩余节点是否与和差值为0
  if (root.left === null && root.right === null) {
    return sum - root.val === 0
  }

  // sum一次减去该节点左节点、右节点 是否等于最后叶子节点
  let left = hasPathSum(root.left, sum - root.val),
    right = hasPathSum(root.right, sum - root.val)

  // 存在一侧满足就满足
  return left || right
}

官方答案

广度优先搜索

  • 题目要求根节点到叶子节点所以如果每遍历一层节点时, 我们找到该层所以的节点,理论上任何一个节点我们都可以与上一节点累加去校验逻辑
  • 现在的问题是,如果只单纯的存储每一层所以的节点,就都是了每个节点的父级节点,不知道了与谁相加
  • 那么尝试在存入节点时就存入处理后的值(借助递归方法中使用的依次减掉已经遇到的节点)

代码实现

  • 声明一个数组 stack 记录每层收集的节点,放入树形数据-第一层(栈-先入先出)
  • 声明一个数组 sumStack 记录每层目标值与累加结果的差值
  • 遍历 stack,只要这一层不全为 null,就一直遍历直到叶子节点终止
  • 取出上一次节点,存入 stack 中节点的左右节点存入做下一层节点
  • 判断 sumStack 存储的差值是否为 0,及为 0 是存入的节点是不是叶子节点

注意

stack 与 sumStack 的数据是一一对应的,遍历中会遍历所有节点及根节点到任意节点的差值

/**
 * 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) {
  if (!root) return false
  let stack = [root],
    sumStack = [sum - root.val]

  while (stack.length) {
    let node = stack.pop(),
      curSum = sumStack.pop()
    if (curSum === 0 && !node.left && !node.right) {
      return true
    }
    if (node.left) {
      stack.push(node.left)
      sumStack.push(curSum - node.left.val)
    }
    if (node.right) {
      stack.push(node.right)
      sumStack.push(curSum - node.right.val)
    }
  }
  return false
}

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:坑人的小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【一天一大 lee】 监控二叉树 (难度:困难)-Day20200922

    遍历二叉树安装摄像头(X),且可被该摄像头监控到的节点标记(Y),未受该节点和其他监控节点监控的节点标记(Z)

    前端小书童
  • 一天一大 lee(克隆图)难度:中等-Day20200812

    图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。

    前端小书童
  • 一天一大 lee(恢复二叉搜索树)难度:困难-Day20200808

    前端小书童
  • 【学习】K近邻算法基础:KD树的操作

    Kd-树概念 Kd-树其实是K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据结构。其实,Kd-树是一种平衡二叉树。 举一示例: 假设...

    小莹莹
  • Zookeeper Shell

    本文主要讲解使用Zookeeper自带的客户端zkCli.sh来进行一些Zookeeper的一些基本操作,如创建删除节点等。

    shysh95
  • ignite TCP发现原理

    节点顺序 - 每个节点的内部属性(对于TcpDiscoverySpi,它只是一个统一增加的数字)。

    lovelife110
  • 分布式Redis深度历险-Cluster

    本文为分布式Redis深度历险系列的第三篇,主要内容为Redis的Cluster,也就是Redis集群功能。

    李红
  • 数据结构:树与二叉树

    一颗高度为h,并含有2^h-1个节点的二叉树称为满二叉树,即树中的每一层都含有最多的节点。

    HLee
  • 分布式Redis深度历险-Cluster

    本文为分布式Redis深度历险系列的第三篇,主要内容为Redis的Cluster,也就是Redis集群功能。

    李红
  • 多叉树 & B树 & B+树 & B*树

    二叉树虽然操作效率比较高,但是如果数据一多,就会有好多好多的节点,需要进行好多次的I/O操作,构建出来的二叉树就会很高很高,也会降低操作速度。

    贪挽懒月

扫码关注云+社区

领取腾讯云代金券