0113. 路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
- 回溯法
- 阿里
- 腾讯
- 百度
- 字节
这道题目是求集合，并不是
求值，而是枚举所有可能，因此动态规划不是特别切合，因此我们需要考虑别的方法。这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的[通用写法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning))，这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路，我画了一张图：
通用写法的具体代码见下方代码区。
- 回溯法
- backtrack 解题公式
- 语言支持：JS，C++，Python3
JavaScript Code：
/*
* @lc app=leetcode id=113 lang=javascript
*
* [113] Path Sum II
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
function backtrack(root, sum, res, tempList) {
if (root === null) return;
if (root.left === null && root.right === null && sum === root.val)
return res.push([...tempList, root.val]);
tempList.push(root.val);
backtrack(root.left, sum - root.val, res, tempList);
backtrack(root.right, sum - root.val, res, tempList);
tempList.pop();
}
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number[][]}
*/
var pathSum = function (root, sum) {
if (root === null) return [];
const res = [];
backtrack(root, sum, res, []);
return res;
};
C++ Code:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
auto ret = vector<vector<int>>();
auto temp = vector<int>();
backtrack(root, sum, ret, temp);
return ret;
}
private:
void backtrack(const TreeNode* root, int sum, vector<vector<int>>& ret, vector<int>& tempList) {
if (root == nullptr) return;
tempList.push_back(root->val);
if (root->val == sum && root->left == nullptr && root->right == nullptr) {
ret.push_back(tempList);
} else {
backtrack(root->left, sum - root->val, ret, tempList);
backtrack(root->right, sum - root->val, ret, tempList);
}
tempList.pop_back();
}
};
# 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]]:
if not root:
return []
result = []
def trace_node(pre_list, left_sum, node):
new_list = pre_list.copy()
new_list.append(node.val)
if not node.left and not node.right:
# 这个判断可以和上面的合并，但分开写会快几毫秒，可以省去一些不必要的判断
if left_sum == node.val:
result.append(new_list)
else:
if node.left:
trace_node(new_list, left_sum-node.val, node.left)
if node.right:
trace_node(new_list, left_sum-node.val, node.right)
trace_node([], sum, root)
return result
最近更新 2yr ago