【Description】
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ /
11 13 4
/ \ /
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]
【Idea】
二叉树题基本是递归解万物？
easy版112，每次recursion少一个path node list的参数即可
【Solution】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.result = []
def pathSum(self, root: TreeNode, sum: int) -> bool:
# DFS & recursion |
def recursion(root, path, cur_sum):
if not root:
return False
if not root.left and not root.right:
if cur_sum+root.val == sum:
path.append(root.val)
self.result.append(copy.deepcopy(path)) # 注意这里需要用深拷贝来append
# print(self.result)
if path:
path.pop()
recursion(root.left, path+[root.val,], cur_sum+root.val)
recursion(root.right, path+[root.val,], cur_sum+root.val)
recursion(root, [], 0)
return self.result
