113. Path Sum II
給定一棵二元樹的根節點和一個整數目標和（targetSum），返回所有從根節點到葉節點的路徑，其中路徑上節點值的總和等於目標和。每條路徑應該作為節點值的列表返回，而不是節點引用。
根到葉的路徑是從根節點開始，到任意葉節點結束的路徑。葉節點是沒有子節點的節點。
範例：
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 輸出：[[5,4,11,2],[5,8,4,5]] 解釋：有兩條路徑的總和等於目標和： 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22
Python
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(node, currentPath, currentSum):
if not node:
return
# Add the current node's value to the path and sum
currentPath.append(node.val)
currentSum += node.val
# Check if it's a leaf node and the current sum equals the target sum
if not node.left and not node.right and currentSum == targetSum:
result.append(list(currentPath))
else:
# Continue the search on the left and right subtrees
dfs(node.left, currentPath, currentSum)
dfs(node.right, currentPath, currentSum)
# Backtrack: remove the current node's value from the path
currentPath.pop()
result = []
dfs(root, [], 0)
return result
17.47MB, 45ms
C++
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
vector<int> currentPath;
dfs(root, targetSum, currentPath, result);
return result;
}
private:
void dfs(TreeNode* node, int targetSum, vector<int>& currentPath, vector<vector<int>>& result) {
if (!node) {
return;
}
// Add the current node's value to the path
currentPath.push_back(node->val);
// Check if it's a leaf node and the current sum equals the target sum
if (!node->left && !node->right && node->val == targetSum) {
result.push_back(currentPath);
} else {
// Continue the search on the left and right subtrees
dfs(node->left, targetSum - node->val, currentPath, result);
dfs(node->right, targetSum - node->val, currentPath, result);
}
// Backtrack: remove the current node's value from the path
currentPath.pop_back();
}
};
18.85MB, 6ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {number[][]}
*/
var pathSum = function(root, targetSum) {
const result = [];
function dfs(node, currentPath, currentSum) {
if (!node) {
return;
}
// Add the current node's value to the path and sum
currentPath.push(node.val);
currentSum += node.val;
// Check if it's a leaf node and the current sum equals the target sum
if (!node.left && !node.right && currentSum === targetSum) {
result.push([...currentPath]);
} else {
// Continue the search on the left and right subtrees
dfs(node.left, currentPath, currentSum);
dfs(node.right, currentPath, currentSum);
}
// Backtrack: remove the current node's value from the path
currentPath.pop();
}
dfs(root, [], 0);
return result;
};
52.28MB, 62ms
