#25. 二叉树的路径总和

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Burger

题目描述

给你二叉树的根节点 和一个表示目标和的整数 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 。如果存在,返回 ;否则,返回

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

输入格式

第一行输入一个整数 ,表示目标和。

第二行输入若干个整数,代表二叉树的层序遍历序列,节点值之间用空格分隔。其中,空节点用特殊值 表示(因二叉树节点值取值范围为 不会与有效节点值冲突)。

若二叉树为空,第二行仅输入一个 即可。

输出格式

输出一行内容,若存在符合条件的根节点到叶子节点的路径,输出 ;否则输出

样例

输入样例

22
5 4 8 11 -1001 13 4 7 2 -1001 -1001 -1001 1

输出样例

true

输入样例

0
-1001

输出样例

false

样例解释

样例1为:

image

数据范围与提示

树中节点的数目在 范围内
节点值取值范围:
目标和取值范围: