题目描述
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
难度:Middle
前置知识
- 回溯法
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这道题目是求集合,并不是求值
,而是枚举所有可能,因此动态规划不是特别切合,因此我们需要考虑别的方法。
这种题目其实有一个通用的解法,就是回溯法。网上也有大神给出了这种回溯法解题的通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路,我画了一张图:
图是 78.subsets,都差不多,仅做参考。
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- 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:
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* 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
相关题目
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com