-
路徑總和 II
給你二叉樹的根節點 root 和一個整數目标和 targetSum ，找出所有 從根節點到葉子節點 路徑總和等于給定目标和的路徑。
葉子節點 是指沒有子節點的節點。
示例 1：
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：[[5,4,11,2],[5,8,4,5]]
示例 2：
輸入：root = [1,2,3], targetSum = 5
輸出：[]
示例 3：
輸入：root = [1,2], targetSum = 0
輸出：[]
提示：
樹中節點總數在範圍 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
方法一：深度優先搜尋
思路及算法
我們可以采用深度優先搜尋的方式，枚舉每一條從根節點到葉子節點的路徑。當我們周遊到葉子節點，且此時路徑和恰為目标和時，我們就找到了一條滿足條件的路徑。
代碼
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
void dfs(TreeNode* root, int targetSum) {
if (root == nullptr) {
return;
}
path.emplace_back(root->val);
targetSum -= root->val;
if (root->left == nullptr && root->right == nullptr && targetSum == 0) {
ret.emplace_back(path);
}
dfs(root->left, targetSum);
dfs(root->right, targetSum);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
dfs(root, targetSum);
return ret;
}
};
複雜度分析
時間複雜度：O(N^2)，其中 N 是樹的節點數。在最壞情況下，樹的上半部分為鍊狀，下半部分為完全二叉樹，并且從根節點到每一個葉子節點的路徑都符合題目要求。此時，路徑的數目為 O(N)O(N)，并且每一條路徑的節點個數也為 O(N)O(N)，是以要将這些路徑全部添加進答案中，時間複雜度為 O(N^2)。
空間複雜度：O(N)，其中 N 是樹的節點數。空間複雜度主要取決于棧空間的開銷，棧中的元素個數不會超過樹的節點數。
方法二：廣度優先搜尋
思路及算法
我們也可以采用廣度優先搜尋的方式，周遊這棵樹。當我們周遊到葉子節點，且此時路徑和恰為目标和時，我們就找到了一條滿足條件的路徑。
為了節省空間，我們使用哈希表記錄樹中的每一個節點的父節點。每次找到一個滿足條件的節點，我們就從該節點出發不斷向父節點疊代，即可還原出從根節點到目前節點的路徑。
class Solution {
public:
vector<vector<int>> ret;
unordered_map<TreeNode*, TreeNode*> parent;
void getPath(TreeNode* node) {
vector<int> tmp;
while (node != nullptr) {
tmp.emplace_back(node->val);
node = parent[node];
}
reverse(tmp.begin(), tmp.end());
ret.emplace_back(tmp);
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return ret;
}
queue<TreeNode*> que_node;
queue<int> que_sum;
que_node.emplace(root);
que_sum.emplace(0);
while (!que_node.empty()) {
TreeNode* node = que_node.front();
que_node.pop();
int rec = que_sum.front() + node->val;
que_sum.pop();
if (node->left == nullptr && node->right == nullptr) {
if (rec == targetSum) {
getPath(node);
}
} else {
if (node->left != nullptr) {
parent[node->left] = node;
que_node.emplace(node->left);
que_sum.emplace(rec);
}
if (node->right != nullptr) {
parent[node->right] = node;
que_node.emplace(node->right);
que_sum.emplace(rec);
}
}
}
return ret;
}
};
複雜度分析
時間複雜度：O(N^2)，其中 N 是樹的節點數。分析思路與方法一相同。
空間複雜度：O(N)，其中 N 是樹的節點數。空間複雜度主要取決于哈希表和隊列空間的開銷，哈希表需要存儲除根節點外的每個節點的父節點，隊列中的元素個數不會超過樹的節點數。
作者：LeetCode-Solution
連結：https://leetcode-cn.com/problems/path-sum-ii/solution/lu-jing-zong-he-ii-by-leetcode-solution/