題目描述
輸入一棵二叉樹和一個(gè)整數(shù)泻拦，打印出二叉樹中節(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑龙填。從樹的根節(jié)點(diǎn)開始往下一直到葉節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)形成一條路徑。
示例
示例 1：
給定如下二叉樹潮饱，以及目標(biāo)和 sum = 22谍婉，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示：
節(jié)點(diǎn)總數(shù) <= 10000
解答方法
方法一：回溯法（先序遍歷+路徑記錄）
思路
先序遍歷： 按照“根、左稚疹、右”的順序居灯，遍歷樹的所有節(jié)點(diǎn)。
路徑記錄： 在先序遍歷中内狗，當(dāng) ① 根節(jié)點(diǎn)到葉節(jié)點(diǎn)形成的路徑 且 ② 路徑各節(jié)點(diǎn)值的和等于目標(biāo)值 sum 時(shí)怪嫌，記錄此路徑。
參考：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/mian-shi-ti-34-er-cha-shu-zhong-he-wei-mou-yi-zh-5/
代碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
path = []
res = []
def dfs(root, sum):
if not root:
return
path.append(root.val)
sum -= root.val
if sum == 0 and not root.left and not root.right:
res.append(path[:])
dfs(root.left, sum)
dfs(root.right, sum)
path.pop()
dfs(root,sum)
return res
時(shí)間復(fù)雜度
O(N) ： N 為二叉樹的節(jié)點(diǎn)數(shù)柳沙，先序遍歷需要遍歷所有節(jié)點(diǎn)岩灭。
空間復(fù)雜度
O(N) ： 最差情況下，即樹退化為鏈表時(shí)赂鲤，path 存儲(chǔ)所有樹節(jié)點(diǎn)噪径，使用O(N) 額外空間。
