【亡羊补牢】挑战数据结构与算法 第40期 LeetCode 437. 路径总和 III(二叉树)
发布日期:2021-06-29 14:34:18
浏览次数:2
分类:技术文章
本文共 1602 字,大约阅读时间需要 5 分钟。
仰望星空的人,不应该被嘲笑
题目描述
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \3 -2 1返回 3。和等于 8 的路径有:1. 5 -> 32. 5 -> 2 -> 13. -3 -> 11
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum-iii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解题思路
本题采用方式就是先序遍历,对于遍历到的每个节点,我们都进行一次 dfs
,但是考虑本题的数字范围为负数,对于当前一条路我们得到了一条路径后,假如后面还有路可以走,那么我们还是继续走,因为后面可能出现正负抵消的情况。
面试中如果遇到题例没有明确说明数字范围,建议和面试官沟通。
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @param {number} sum * @return {number} */var pathSum = function (root, sum) { // 定义一个计时器 let cnt = 0; // 先序遍历所有根节点 let preOrder = (root, sum) => { if (root == null) return; dfs(root, sum); preOrder(root.left, sum); preOrder(root.right, sum); } let dfs = (root, sum) => { if (root == null) return; sum -= root.val; // 求和满足,累加 if (sum === 0) cnt++; // 递归左右子树,如果当前和为0了,但是下面还是有路,还是继续走下去 // 因为本题数值范围存在负数,可能继续走下去还存在满足条件的路径 dfs(root.left, sum); dfs(root.right, sum); } preOrder(root, sum); return cnt;};
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/108788868 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月03日 16时39分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Linux入门常用命令
2019-04-29
Spring整理
2019-04-29
SpringMvc加强
2019-04-29
初识Vue全家桶 Nuxt.js(一)
2019-04-29
基本路由及动态路由(二)
2019-04-29
视图:默认模板+默认布局(自定义布局)+nuxt.js页面(三)
2019-04-29
基于nuxt下asyncData,fetch发送axios请求(四)
2019-04-29
插件机制+自定义axios(五)
2019-04-29
Redis的学习之路
2019-04-29
Windows下Redies+GUI安装,使用Jedis与spring boot 整合
2019-04-29
Windows创建本地版本库(1)
2019-04-29
基于java的酒店管理系统的设计与实现
2019-04-29
基于WEB的仓库管理系统的设计与实现
2019-04-29
基于java的web聊天系统
2019-04-29
基于java的俄罗斯方块的设计与实现
2019-04-29
基于java的魂斗罗的设计
2019-04-29
基于java的网页内容管理
2019-04-29
基于java的学生管理系统
2019-04-29
基于java网盘搜索的设计与实现
2019-04-29