题目地址
https://leetcode.com/problems/path-sum-ii/description/
题目描述
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]
思路
这道题目是求集合,并不是求值
,而是枚举所有可能,因此动态规划不是特别切合,因此我们需要考虑别的方法。
这种题目其实有一个通用的解法,就是回溯法。
网上也有大神给出了这种回溯法解题的
通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路,我画了一张图:
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- 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
相关题目
- 39.combination-sum
- 40.combination-sum-ii
- 46.permutations
- 47.permutations-ii
- 78.subsets
- 90.subsets-ii
- 131.palindrome-partitioning
题目地址 https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/description/ 题目描述 在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。 如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标…
LeetCode题解1031.maximum-sum-of-two-non-overlapping-subarrays题目地址 https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/ 题目描述 Given an array A of non-negative integers, return the maximum sum of elements in two non-overl…
LeetCode题解堆排序和快速排序堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧
我的遍历遍历有什么问题? - java我正在尝试解决此问题https://oj.leetcode.com/problems/binary-tree-preorder-traversal/,即使用递归解决方案进行预遍历。编辑:整个代码:import java.util.ArrayList; import java.util.List; public class Solution { public …
LeetCode题解斜着遍历遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索, 而搜索的核心就是遍历,而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能,而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候, 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历, 更少有情况是斜着遍历。那么这次就考考你, 怎么斜着遍历一个二…