Path Sum to Target in Binary Tree
1. Link
2. 描述
给定一个二叉树和一个值\ sum sum,判断是否有从根节点到叶子节点的节点值之和等于\ sum sum 的路径,
例如:
给出如下的二叉树,\ sum=22 sum=22,
返回true,因为存在一条路径 5\to 4\to 11\to 25→4→11→2的节点值之和为 22
示例1
输入:
{1,2},0
复制返回值:
false
复制
示例2
输入:
{1,2},3
复制返回值:
true
3. 思路
idea: recursion
check if node is none, return False,
if node is leaf node and target== node.val,return True, otherwise False
search the left and right tree path and then use OR to combine their results to check if the path exist
Time: O(n) to iterate every tree node
Space: O(height of tree)
4. Coding
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param root TreeNode类
# @param sum int整型
# @return bool布尔型
#
class Solution:
def hasPathSum(self , root , sum ):
# write code here
#input: root, target
# idea: recursion
# 1. input: node, current target
# 2. if node is leaf node and target is 0, -> return True (found a path from root to leaf), otherwise, False
# 3. update target by target - node.val
# 4. go to left, right subtree to find the path
#
#
if not root or sum ==None:
return False
return self.findpath(root, sum)
def findpath(self, node, target):
# if node is invalid
if not node:
return False
# if node is leaf node
if node and not node.left and not node.right:
if target == node.val:
return True
return False
# exist a path
return self.findpath(node.left, target-node.val) or self.findpath(node.right, target-node.val)
Last updated
Was this helpful?