題目

標(biāo)題和出處

標(biāo)題：路徑總和 II

出處：113. 路徑總和 II

難度

4 級

題目描述

要求

給你二叉樹的根結(jié)點(diǎn) $\text{root}$ 和一個表示目標(biāo)和的整數(shù) $\text{targetSum}$，返回所有的滿足路徑上結(jié)點(diǎn)值總和等于目標(biāo)和 $\text{targetSum}$ 的從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑。每條路徑應(yīng)該以結(jié)點(diǎn)值列表的形式返回，而不是結(jié)點(diǎn)的引用。

示例

示例 1：

輸入：$\text{root?=?[5,4,8,11,null,13,4,7,2,null,null,5,1],?targetSum?=?22}$
輸出：$\text{[[5,4,11,2],[5,8,4,5]]}$
解釋：有兩條路徑的結(jié)點(diǎn)值總和等于 $\text{targetSum}$：
$\text{5?+?4?+?11?+?2?=?22}$
$\text{5?+?8?+?4?+?5?=?22}$

示例 2：

輸入：$\text{root?=?[1,2,3],?targetSum?=?5}$
輸出：$\text{[]}$

示例 3：

輸入：$\text{root?=?[1,2],?targetSum?=?0}$
輸出：$\text{[]}$

數(shù)據(jù)范圍

• 樹中結(jié)點(diǎn)數(shù)目在范圍 $\text{[0,?5000]}$ 內(nèi)
• $\text{-1000}\le \text{Node.val}\le \text{1000}$
• $\text{-1000}\le \text{targetSum}\le \text{1000}$

前言

這道題是「路徑總和」的進(jìn)階，要求返回所有的結(jié)點(diǎn)值總和等于目標(biāo)和的從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑。這道題也可以使用深度優(yōu)先搜索和廣度優(yōu)先搜索得到答案，在搜索過程中需要維護(hù)路徑。

解法一

思路和算法

如果二叉樹為空，則不存在結(jié)點(diǎn)值總和等于目標(biāo)和的路徑。只有當(dāng)二叉樹不為空時，才可能存在結(jié)點(diǎn)值總和等于目標(biāo)和的路徑，需要從根結(jié)點(diǎn)開始尋找路徑。

從根結(jié)點(diǎn)開始深度優(yōu)先搜索，在遍歷每一個結(jié)點(diǎn)的同時需要維護(hù)從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑以及剩余目標(biāo)和，將原目標(biāo)和減去當(dāng)前結(jié)點(diǎn)值即可得到剩余目標(biāo)和。當(dāng)訪問到葉結(jié)點(diǎn)時，如果剩余目標(biāo)和為 $0$，則從根結(jié)點(diǎn)到當(dāng)前葉結(jié)點(diǎn)的路徑即為結(jié)點(diǎn)值總和等于目標(biāo)和的路徑，將該路徑添加到結(jié)果列表中。

由于深度優(yōu)先搜索過程中維護(hù)的路徑會隨著訪問到的結(jié)點(diǎn)而變化，因此當(dāng)找到結(jié)點(diǎn)值總和等于目標(biāo)和的路徑時，需要新建一個路徑對象添加到結(jié)果列表中，避免后續(xù)搜索過程中路徑變化對結(jié)果造成影響。

代碼

class Solution {List<List<Integer>> paths = new ArrayList<List<Integer>>();List<Integer> path = new ArrayList<Integer>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {dfs(root, targetSum);return paths;}public void dfs(TreeNode node, int targetSum) {if (node == null) {return;}path.add(node.val);targetSum -= node.val;if (node.left == null && node.right == null && targetSum == 0) {paths.add(new ArrayList<Integer>(path));}dfs(node.left, targetSum);dfs(node.right, targetSum);path.remove(path.size() - 1);}
}

復(fù)雜度分析

• 時間復(fù)雜度：$O(n^2)$，其中 $n$ 是二叉樹的結(jié)點(diǎn)數(shù)。每個結(jié)點(diǎn)都被訪問一次，最壞情況下每次將路徑添加到結(jié)果中的時間是 $O(n)$，因此總時間復(fù)雜度是 $O(n^2)$。

• 空間復(fù)雜度：$O(n)$，其中 $n$ 是二叉樹的結(jié)點(diǎn)數(shù)?？臻g復(fù)雜度主要是遞歸調(diào)用的?？臻g以及深度優(yōu)先搜索過程中存儲路徑的空間，取決于二叉樹的高度，最壞情況下二叉樹的高度是 $O(n)$。注意返回值不計入空間復(fù)雜度。

解法二

思路和算法

使用廣度優(yōu)先搜索尋找結(jié)點(diǎn)值總和等于目標(biāo)和的路徑時，首先找到這些路徑對應(yīng)的葉結(jié)點(diǎn)，然后得到從葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，將路徑翻轉(zhuǎn)之后即可得到相應(yīng)的路徑。

為了得到從葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，需要使用哈希表存儲每個結(jié)點(diǎn)的父結(jié)點(diǎn)，在廣度優(yōu)先搜索的過程中即可將每個結(jié)點(diǎn)和父結(jié)點(diǎn)的關(guān)系存入哈希表中。

廣度優(yōu)先搜索需要維護(hù)兩個隊列，分別存儲結(jié)點(diǎn)與對應(yīng)的結(jié)點(diǎn)值總和。廣度優(yōu)先搜索的過程中，如果遇到一個葉結(jié)點(diǎn)對應(yīng)的結(jié)點(diǎn)值總和等于目標(biāo)和，則找到一條結(jié)點(diǎn)值總和等于目標(biāo)和的路徑，利用哈希表中存儲的父結(jié)點(diǎn)信息得到從當(dāng)前葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，然后將路徑翻轉(zhuǎn)，添加到結(jié)果中。

代碼

class Solution {List<List<Integer>> paths = new ArrayList<List<Integer>>();Map<TreeNode, TreeNode> parents = new HashMap<TreeNode, TreeNode>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if (root == null) {return paths;}Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();Queue<Integer> sumQueue = new ArrayDeque<Integer>();nodeQueue.offer(root);sumQueue.offer(root.val);while (!nodeQueue.isEmpty()) {TreeNode node = nodeQueue.poll();int sum = sumQueue.poll();TreeNode left = node.left, right = node.right;if (left == null && right == null && sum == targetSum) {paths.add(getPath(node));}if (left != null) {parents.put(left, node);nodeQueue.offer(left);sumQueue.offer(sum + left.val);}if (right != null) {parents.put(right, node);nodeQueue.offer(right);sumQueue.offer(sum + right.val);}}return paths;}public List<Integer> getPath(TreeNode node) {List<Integer> path = new ArrayList<Integer>();while (node != null) {path.add(node.val);node = parents.get(node);}Collections.reverse(path);return path;}
}

復(fù)雜度分析

• 時間復(fù)雜度：$O(n^2)$，其中 $n$ 是二叉樹的結(jié)點(diǎn)數(shù)。每個結(jié)點(diǎn)都被訪問一次，最壞情況下每次將路徑添加到結(jié)果中的時間是 $O(n)$，因此總時間復(fù)雜度是 $O(n^2)$。

• 空間復(fù)雜度：$O(n)$，其中 $n$ 是二叉樹的結(jié)點(diǎn)數(shù)。空間復(fù)雜度主要是哈希表和隊列空間，哈希表需要存儲每個結(jié)點(diǎn)的父結(jié)點(diǎn)，需要 $O(n)$ 的空間，兩個隊列內(nèi)元素個數(shù)都不超過 $n$。注意返回值不計入空間復(fù)雜度。