路径总和

路径总和

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

示例

给定如下二叉树,以及目标和sum = 22,返回true,因为存在目标和为22的根节点到叶子节点的路径5->4->11->2

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

题解

/**
 * 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) {
    return dfs(root, sum, 0); 
};

function dfs(root, sum, tmp){
    if(!root) return false;
    tmp = tmp + root.val;
    if(!root.left && !root.right) return tmp === sum ;
    return dfs(root.left, sum, tmp) || dfs(root.right, sum, tmp);
}

思路

深度优先遍历即可,首先处理边界条件,如果节点为null则直接返回false,之后将tmp值与节点值相加,如果此节点为根节点,那么就返回tmp是否与sum相等的判断,最后进行深度递归遍历,利用短路运算效应,在左子树为true的情况下不会再进行右子树的递归运算,在右子树为true的情况下会直接返回上层递归运算,这样即可实现路径总和的计算。

每日一题

https://github.com/WindrunnerMax/EveryDay

题源

https://leetcode-cn.com/problems/path-sum

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树的最小深度

    给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。

    WindrunnerMax
  • 跳水板

    你正在使用一堆木板建造跳水板。有两种类型的木板,其中长度较短的木板长度为shorter,长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法,...

    WindrunnerMax
  • 翻转二叉树

    本题是经典的二叉树操作的题目,直接从根节点进行递归遍历,并从叶子节点进行翻转,如果当前遍历到root,那么只需要继续交换两棵子树的位置即可完成翻转,首先判断节点...

    WindrunnerMax
  • 【关关的刷题日记60】Leetcode 437. Path Sum III

    关关的刷题日记60 – Leetcode 437. Path Sum III 题目 ? 题目的意思是给定一个二叉树,让我们找到路径节点和等于给定值的路径的个数。...

    WZEARW
  • 【HTB系列】靶机Teacher的渗透测试详解

    第一个img元素多了一个onerror错误事件,意思是加载错误时在控制台输出(That‘s an F)

    徐焱
  • Minifilter的动态安装、加载及卸载

    MINIFILTER框架的文件系统过滤驱动,无法使用的CreateService和OpenService进行动态加载。 看了一下,使用Inf文件安装Minif...

    战神伽罗
  • 每日算法系列【LeetCode 685】冗余连接 II

    在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。每一个节点只有一个父节点,除了根节点没有父节点。

    godweiyang
  • Tree - 110. Balanced Binary Tree

    Given a binary tree, determine if it is height-balanced.

    用户5705150
  • [LeetCode] 938. Range Sum of BST 二叉搜索树的区间和

    Given the root node of a binary search tree, return the sum of values of all nod...

    lucifer210
  • Flutter异步编程async与await的基本使用

    异步编程常用于网络请求、缓存数据加载、本地File图片加载、定时与延时任务等,在Flutter开发中 ,使用async开启一个异步开始处理,使用await来等待...

    早起的年轻人

扫码关注云+社区

领取腾讯云代金券