題目描述
給定一個(gè)二叉樹和一個(gè)目標(biāo)和滤港，判斷該樹中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑眯勾，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和湃番。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)席吴。
示例:
給定如下二叉樹赌结，以及目標(biāo)和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因?yàn)榇嬖谀繕?biāo)和為 22 的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑 5->4->11->2孝冒。
知識(shí)點(diǎn)
二叉樹柬姚、遞歸
Qiang的思路
# 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, cur=0) -> bool:
if root==None:
return False
if root.left!=None or root.right!=None:
return self.hasPathSum(root.left, sum, cur+root.val) or self.hasPathSum(root.right, sum, cur+root.val)
return True if cur+root.val==sum else False
作者原創(chuàng)，如需轉(zhuǎn)載及其他問題請(qǐng)郵箱聯(lián)系：lwqiang_chn@163.com庄涡。
個(gè)人網(wǎng)站：https://www.myqiang.top量承。
