LeetCode 113: Path Sum II (DFS Backtracking Path Capture)
LeetCode 113Binary TreeBacktrackingToday we solve LeetCode 113 - Path Sum II.
Source: https://leetcode.com/problems/path-sum-ii/
English
Problem Summary
Given a binary tree root and an integer targetSum, return all root-to-leaf paths where the sum of node values equals targetSum.
Key Insight
Use DFS with one mutable path list and a running remainder. Push current node before exploring children, pop when returning (backtracking). Record a copy only when at leaf and remainder becomes zero.
Brute Force and Limitations
You can enumerate all root-to-leaf paths first and then filter by sum. That works, but creates unnecessary path copies. DFS + backtracking keeps one active path and copies only valid answers.
Optimal Algorithm Steps (DFS + Backtracking)
1) If node is null, return.
2) Add node value into path, subtract from remainder.
3) If node is leaf and remainder is 0, append path snapshot to result.
4) Recurse into left and right children.
5) Pop current value before returning to parent.
Complexity Analysis
Time: O(n + kL), where n is nodes, k is number of valid paths, L is average copied path length.
Space: O(h) recursion stack + O(h) active path (excluding output).
Common Pitfalls
- Accepting non-leaf nodes as valid path endings.
- Forgetting to pop when backtracking, causing path contamination.
- Appending the same mutable path reference instead of a copied snapshot.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(root, targetSum, path, ans);
return ans;
}
private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> ans) {
if (node == null) return;
path.add(node.val);
remain -= node.val;
if (node.left == null && node.right == null && remain == 0) {
ans.add(new ArrayList<>(path));
} else {
dfs(node.left, remain, path, ans);
dfs(node.right, remain, path, ans);
}
path.remove(path.size() - 1);
}
}/**
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) [][]int {
ans := [][]int{}
path := []int{}
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, remain int) {
if node == nil {
return
}
path = append(path, node.Val)
remain -= node.Val
if node.Left == nil && node.Right == nil && remain == 0 {
snapshot := append([]int(nil), path...)
ans = append(ans, snapshot)
} else {
dfs(node.Left, remain)
dfs(node.Right, remain)
}
path = path[:len(path)-1]
}
dfs(root, targetSum)
return ans
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> ans;
vector<int> path;
dfs(root, targetSum, path, ans);
return ans;
}
private:
void dfs(TreeNode* node, long long remain, vector<int>& path, vector<vector<int>>& ans) {
if (node == nullptr) return;
path.push_back(node->val);
remain -= node->val;
if (node->left == nullptr && node->right == nullptr && remain == 0) {
ans.push_back(path);
} else {
dfs(node->left, remain, path, ans);
dfs(node->right, remain, path, ans);
}
path.pop_back();
}
};# 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]]:
ans = []
path = []
def dfs(node: Optional[TreeNode], remain: int) -> None:
if node is None:
return
path.append(node.val)
remain -= node.val
if node.left is None and node.right is None and remain == 0:
ans.append(path[:])
else:
dfs(node.left, remain)
dfs(node.right, remain)
path.pop()
dfs(root, targetSum)
return ans/**
* 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)
* }
*/
var pathSum = function(root, targetSum) {
const ans = [];
const path = [];
const dfs = (node, remain) => {
if (node === null) return;
path.push(node.val);
remain -= node.val;
if (node.left === null && node.right === null && remain === 0) {
ans.push([...path]);
} else {
dfs(node.left, remain);
dfs(node.right, remain);
}
path.pop();
};
dfs(root, targetSum);
return ans;
};中文
题目概述
给定二叉树根节点和整数 targetSum，返回所有从根到叶子且路径和等于 targetSum 的路径。
核心思路
使用 DFS + 回溯：维护一条当前路径 path 和剩余目标值 remain。进入节点时 push，回溯时 pop；只有到叶子且 remain == 0 才把当前路径拷贝进答案。
基线解法与不足
先枚举所有根到叶子的路径再筛选也能做，但会产生很多无效路径拷贝。回溯写法仅在命中答案时才复制，空间更经济。
最优算法步骤（DFS + 回溯）
1）节点为空直接返回。
2）把当前节点加入路径，并从 remain 扣除节点值。
3）若当前是叶子且 remain == 0，将路径快照加入结果。
4）递归左右子树继续搜索。
5）函数返回前弹出当前节点，恢复现场。
复杂度分析
时间复杂度：O(n + kL)，n 为节点数，k 为合法路径条数，L 为平均路径长度。
空间复杂度：O(h) 递归栈 + O(h) 当前路径（不含输出）。
常见陷阱
- 把“到任意节点”误判为合法，忽略“必须到叶子”。
- 回溯忘记 pop，导致路径串味。
- 直接存入可变路径对象，后续修改污染历史答案。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(root, targetSum, path, ans);
return ans;
}
private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> ans) {
if (node == null) return;
path.add(node.val);
remain -= node.val;
if (node.left == null && node.right == null && remain == 0) {
ans.add(new ArrayList<>(path));
} else {
dfs(node.left, remain, path, ans);
dfs(node.right, remain, path, ans);
}
path.remove(path.size() - 1);
}
}/**
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) [][]int {
ans := [][]int{}
path := []int{}
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, remain int) {
if node == nil {
return
}
path = append(path, node.Val)
remain -= node.Val
if node.Left == nil && node.Right == nil && remain == 0 {
snapshot := append([]int(nil), path...)
ans = append(ans, snapshot)
} else {
dfs(node.Left, remain)
dfs(node.Right, remain)
}
path = path[:len(path)-1]
}
dfs(root, targetSum)
return ans
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> ans;
vector<int> path;
dfs(root, targetSum, path, ans);
return ans;
}
private:
void dfs(TreeNode* node, long long remain, vector<int>& path, vector<vector<int>>& ans) {
if (node == nullptr) return;
path.push_back(node->val);
remain -= node->val;
if (node->left == nullptr && node->right == nullptr && remain == 0) {
ans.push_back(path);
} else {
dfs(node->left, remain, path, ans);
dfs(node->right, remain, path, ans);
}
path.pop_back();
}
};# 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]]:
ans = []
path = []
def dfs(node: Optional[TreeNode], remain: int) -> None:
if node is None:
return
path.append(node.val)
remain -= node.val
if node.left is None and node.right is None and remain == 0:
ans.append(path[:])
else:
dfs(node.left, remain)
dfs(node.right, remain)
path.pop()
dfs(root, targetSum)
return ans/**
* 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)
* }
*/
var pathSum = function(root, targetSum) {
const ans = [];
const path = [];
const dfs = (node, remain) => {
if (node === null) return;
path.push(node.val);
remain -= node.val;
if (node.left === null && node.right === null && remain === 0) {
ans.push([...path]);
} else {
dfs(node.left, remain);
dfs(node.right, remain);
}
path.pop();
};
dfs(root, targetSum);
return ans;
};
Comments