【亡羊补牢】挑战数据结构与算法 第40期 LeetCode 437. 路径总和 III(二叉树)
发布日期:2021-06-29 14:34:18
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月06日 23时28分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
电动汽车的“专属危险”:网络威胁问题不容小觑
2019-04-29
短暂的告别,马上再回来
2019-04-29
统治50年:为什么SQL在如今仍然很重要?
2019-04-29
测试是一场竞争,而数据每次都会获得胜利
2019-04-29
读心的测谎系统:究竟是骗子还是个天才?
2019-04-29
最大规模技术重建:数据库连接从15000个到100个以下
2019-04-29
复工之后:员工如何改善网络安全?
2019-04-29
70%求职者因此被拒,你还不避开这些“雷区”?!
2019-04-29
办法不在多,有用就行!用Dropout解决过度拟合问题
2019-04-29
色情演员识别?绝对是人脸识别最糟糕的应用……
2019-04-29
让强化学习逃离“乏味区域陷阱”,试着加点噪音吧!
2019-04-29
超详细Spring Boot面试问题集锦,死角一个不留!
2019-04-29
10个业余时间可完成的项目,助你飞速提升编码能力!
2019-04-29
网络爬虫初涉——用python爬取网络小说
2019-04-29
Pycharm+tensorflow dropout 学习(三)
2019-04-29
Pycharm+tensorflow CNN 学习(四)
2019-04-29
用python暴力破解压缩包密码
2019-04-29
基于OpenCV 将图片进行预处理,转变为MNIST图片格式
2019-04-29
PyCharm+Tensorflow CNN调用训练好的模型进行预测 (五)
2019-04-29
物联网平台Node-red初涉——访问搭建的简易服务器
2019-04-29