找出一棵二叉樹所有的從根節點到某一葉子節點的路徑,該路徑上所有節點的和為一個特定值。
注意點:
無例子:
輸入:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
輸出:
[
[5,4,11,2],
[5,8,4,5]
]
Path Sum 是判斷是否有這樣一條路徑,現在要把所有的路徑都求出來,那只要在dfs時將符合要求的路徑加入到結果集。注意加入結果集的數據不要是引用,否則可能之後會再次被修改。
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
result = []
self._pathSum(root, sum, [], result)
return result
def _pathSum(self, root, sum, curr, result):
if not root:
return
sum -= root.val
if sum == 0 and root.left is None and root.right is None:
result.append(curr + [root.val])
if root.left:
self._pathSum(root.left, sum, curr + [root.val], result)
if root.right:
self._pathSum(root.right, sum, curr + [root.val], result)
if __name__ == "__main__":
None