Leecode刷题之旅-C语言/python-112 路径总和
2024-10-19 04:24:02
/*
* @lc app=leetcode.cn id=112 lang=c
*
* [112] 路径总和
*
* https://leetcode-cn.com/problems/path-sum/description/
*
* algorithms
* Easy (45.08%)
* Total Accepted: 12.4K
* Total Submissions: 27.5K
* Testcase Example: '[5,4,8,11,null,13,4,7,2,null,null,null,1]\n22'
*
* 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
*
* 说明: 叶子节点是指没有子节点的节点。
*
* 示例:
* 给定如下二叉树,以及目标和 sum = 22,
*
* 5
* / \
* 4 8
* / / \
* 11 13 4
* / \ \
* 7 2 1
*
*
* 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
*
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool hasPathSum(struct TreeNode* root, int sum) {
if(root==NULL){
return false;
}
if(root->left==NULL&&root->right==NULL){
return root->val==sum;
}
return hasPathSum(root->left,sum-root->val)||
hasPathSum(root->right,sum-root->val);
}
这里进行迭代,每次都用sum减去左子树或是右子树的值。
#
# @lc app=leetcode.cn id=112 lang=python3
#
# [112] 路径总和
#
# https://leetcode-cn.com/problems/path-sum/description/
#
# algorithms
# Easy (45.08%)
# Total Accepted: 12.4K
# Total Submissions: 27.5K
# Testcase Example: '[5,4,8,11,null,13,4,7,2,null,null,null,1]\n22'
#
# 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
#
# 说明: 叶子节点是指没有子节点的节点。
#
# 示例:
# 给定如下二叉树,以及目标和 sum = 22,
#
# 5
# / \
# 4 8
# / / \
# 11 13 4
# / \ \
# 7 2 1
#
#
# 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
#
#
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
if not root.left and not root.right and root.val == sum:
return True
sum -= root.val
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
最新文章
- 各种浏览器的Hack写法(chrome firefox ie等)
- Android缓存学习入门
- [百度空间] [原] 全局operator delete重载到DLL
- JQuery处理json与ajax返回JSON实例
- cocos2dx windows phone平台下CCLabelTTF自己主动换行的实现(2)
- 抓取Bing每日图片作为网站首页背景
- 再探java基础——对面向对象的理解(1)
- linux ftp 安装及相关命令
- java提高篇(八)-----实现多重继承
- TempDB问题定位与解决
- Matplotlib初体验
- 如何通过java反射的方式对java私有方法进行单元测试
- POSIX 消息队列相关问题
- Windows 下自动同步文件夹内容到另一个文件夹下
- day05流程控制while循环 流程控制for循环
- 背水一战 Windows 10 (40) - 控件(导航类): AppBar, CommandBar
- 当vcenter是linux版本的时候Sysprep存放路径
- yaf windows安装
- linux自建git仓库
- 『转』Panda Antivirus Pro 2014 – 免费6个月