daily leetcode - path-sum-ii - !
题目地址
https://leetcode.com/problems/path-sum-ii/
题目描述
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For 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]
]
思路
这道二叉树路径之和在之前那道题 Path Sum 的基础上又需要找出路径,但是基本思想都一样,还是需要用深度优先搜索 DFS,只不过数据结构相对复杂一点,需要用到二维的 vector,而且每当 DFS 搜索到新结点时,都要保存该结点。而且每当找出一条路径之后,都将这个保存为一维 vector 的路径保存到最终结果二维 vector 中。并且,每当 DFS 搜索到子结点,发现不是路径和时,返回上一个结点时,需要把该结点从一维 vector 中移除,参见代码如下:
解法一:
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> out;
helper(root, sum, out, res);
return res;
}
void helper(TreeNode* node, int sum, vector<int>& out, vector<vector<int>>& res) {
if (!node) return;
out.push_back(node->val);
if (sum == node->val && !node->left && !node->right) {
res.push_back(out);
}
helper(node->left, sum - node->val, out, res);
helper(node->right, sum - node->val, out, res);
out.pop_back();
}
};
下面这种方法是迭代的写法,用的是中序遍历的顺序,参考之前那道 Binary Tree Inorder Traversal,中序遍历本来是要用栈来辅助运算的,由于要取出路径上的结点值,所以用一个 vector 来代替 stack,首先利用 while 循环找到最左子结点,在找的过程中,把路径中的结点值都加起来,这时候取出 vector 中的尾元素,如果其左右子结点都不存在且当前累加值正好等于 sum 了,将这条路径取出来存入结果 res 中,下面的部分是和一般的迭代中序写法有所不同的地方,由于中序遍历的特点,遍历到当前结点的时候,是有两种情况的,有可能此时是从左子结点跳回来的,此时正要去右子结点,则当前的结点值还是算在路径中的;也有可能当前是从右子结点跳回来的,并且此时要跳回上一个结点去,此时就要减去当前结点值,因为其已经不属于路径中的结点了。为了区分这两种情况,这里使用一个额外指针 pre 来指向前一个结点,如果右子结点存在且不等于 pre,直接将指针移到右子结点,反之更新 pre 为 cur,cur 重置为空,val 减去当前结点,st 删掉最后一个结点,参见代码如下:
解法二:
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<TreeNode*> st;
TreeNode *cur = root, *pre = nullptr;
int val = 0;
while (cur || !st.empty()) {
while (cur) {
st.push_back(cur);
val += cur->val;
cur = cur->left;
}
cur = st.back();
if (!cur->left && !cur->right && val == sum) {
vector<int> v;
for (auto &a : st) v.push_back(a->val);
res.push_back(v);
}
if (cur->right && cur->right != pre) {
cur = cur->right;
} else {
pre = cur;
val -= cur->val;
st.pop_back();
cur = nullptr;
}
}
return res;
}
};
思路2
这道题目是求集合,并不是求值
,而是枚举所有可能,因此动态规划不是特别切合,因此我们需要考虑别的方法。
这种题目其实有一个通用的解法,就是回溯法。
网上也有大神给出了这种回溯法解题的
通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路,我画了一张图:
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- 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
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode