PathSumII [source code]
public class PathSumII {
static
/******************************************************************************/
class Solution {
public List<List<Integer>> pathSum (TreeNode root, int sum) {
if (root == null)
return new LinkedList<> ();
List<List<Integer>> lss = new LinkedList<> ();
List<List<Integer>> left_lss = pathSum (root.left, sum - root.val), right_lss = pathSum (root.right, sum - root.val);
for (List<Integer> ls : left_lss) {
ls.add (0, root.val);
lss.add (ls);
}
for (List<Integer> ls : right_lss) {
ls.add (0, root.val);
lss.add (ls);
}
if (lss.isEmpty () && !((root.left == null) ^ (left_lss.isEmpty ())) && !((root.right == null) ^ (right_lss.isEmpty ())) && root.val == sum) {
List<Integer> ls = new LinkedList<> ();
ls.add (root.val);
lss.add (ls);
}
return lss;
}
}
/******************************************************************************/
public static void main(String[] args) {
PathSumII.Solution tester = new PathSumII.Solution();
}
}
没有说所有的node都是正数, 所以好像没有什么prune的办法; 规定了必须是root到leaf的, 所以这个题其实不是很难? 要去重吗? 应该不要, 只要顺序不一样, 就算element是一样的, 也应该算作是不同的path;
returned recursion应该好写;
感觉思路很简单的一个题目, 最后居然超时了; 一个难点在于, 你一个subtree, 如果是Null, 也是返回failure, 如果是不Empty, 但是就是找不到这样的path, 也是failure, 你怎么区分这两种failure?
最后我的做法是整个就不return Null; 感觉没什么用; 所有的failure都返回Empty list; 假如发现自己的两边返回上来的都是Empty, 同时自己的value等于sum, 那么这个时候不是一定就能把自己的value做成一个list加到结果里面去的: 必须确定自己是leaf才行!
这么一说发现自己上面写的反而搞复杂了, 最后一个if的header不需要xor, 直接lss.isEmpty () && root.left == null && root.right == null && root.val == sum就行了;
速度是6ms (13%).
没有editorial;
public List<List<Integer>> pathSum(TreeNode root, int sum){
List<List<Integer>> result = new LinkedList<List<Integer>>();
List<Integer> currentResult = new LinkedList<Integer>();
pathSum(root,sum,currentResult,result);
return result;
}
public void pathSum(TreeNode root, int sum, List<Integer> currentResult,
List<List<Integer>> result) {
if (root == null)
return;
currentResult.add(new Integer(root.val));
if (root.left == null && root.right == null && sum == root.val) {
result.add(new LinkedList(currentResult));
currentResult.remove(currentResult.size() - 1);//don't forget to remove the last integer
return;
} else {
pathSum(root.left, sum - root.val, currentResult, result);
pathSum(root.right, sum - root.val, currentResult, result);
}
currentResult.remove(currentResult.size() - 1);
}
非要用mutation recursion, 所以最后就是需要一个helper;
注意他这里是直接在pre Null的位置判断; 只有两头Null的时候, 才单独加root; 否则, 哪怕是一头Null, 也直接分别recurse, 最后得到什么就是什么, 反正不强行加单独root的list;
Nice solution with back-tracking. I think you could make it more elegant by removing
currentResult.remove(currentResult.size() - 1);//don't forget to remove the last integer
return;
This is because after finishing the statements in if, we will never walk into else. So it is not necessary to use return here.
有点道理;
Also using ArrayList allows O(1) access to the each node, that means removing the last element takes only O(1). If you use LinkedList, initially we have traverse the list to the last node then remove it, which takes O(n) time. I guess this is what @firesum is trying to suggest.
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>>ret = new ArrayList<List<Integer>>();
List<Integer> cur = new ArrayList<Integer>();
pathSum(root, sum, cur, ret);
return ret;
}
public void pathSum(TreeNode root, int sum, List<Integer>cur, List<List<Integer>>ret){
if (root == null){
return;
}
cur.add(root.val);
if (root.left == null && root.right == null && root.val == sum){
ret.add(new ArrayList(cur));
}else{
pathSum(root.left, sum - root.val, cur, ret);
pathSum(root.right, sum - root.val, cur, ret);
}
cur.remove(cur.size()-1);
}
```java
> In my test, the revised version takes 380ms while the original version takes 464ms.
因为是backtracking, 所以指针和copy之间的关系的问题又出现了;
> This is the backtracking point. If we execute two sub recursive code in else branch and still can’t get a match pathSum, this means the current “root” which already added into the List currentResult can not lead us to the correct answer. So we need to remove it from List currentResult and try other possible branches, this is what backtracking means.
> The time complexity of this solution is O(n). It is the same time complexity as that of recursive in-order traversal. An intuitive way to arrive at this answer is asking: how many times does each node in the tree get operated/visited on? The answer is 1 time per node.
> If you really want to be thorough in explaining to interviewer, one could say: it would be O(n) + O(p h) where p is the number of root to leaf paths and h is the height of the tree. The reason we include O(p*h) is because of the
> result.add(new LinkedList(currentResult));
> For each possible path, we have to make a deep copy of this list, which takes O(h) for one path and there are p such paths. But O(n) + O(ph) would be O(n).
---
https://leetcode.com/problems/path-sum-ii/discuss/36685/12ms-11-lines-C++-Solution
> Well, a typical backtracking problem. The code is as follows. You may walk through it using the example in the problem statement to see how it works.
```c++
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int> > paths;
vector<int> path;
findPaths(root, sum, path, paths);
return paths;
}
private:
void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
if (!node) return;
path.push_back(node -> val);
if (!(node -> left) && !(node -> right) && sum == node -> val)
paths.push_back(path);
findPaths(node -> left, sum - node -> val, path, paths);
findPaths(node -> right, sum - node -> val, path, paths);
path.pop_back();
}
};
代码写的比较干净;
https://leetcode.com/problems/path-sum-ii/discuss/36695/Java-Solution:-iterative-and-recursive
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
int SUM = 0;
TreeNode cur = root;
TreeNode pre = null;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
path.add(cur.val);
SUM+=cur.val;
cur=cur.left;
}
cur = stack.peek();
if(cur.right!=null && cur.right!=pre){
cur = cur.right;
continue;
}
if(cur.left==null && cur.right==null && SUM==sum)
res.add(new ArrayList<Integer>(path));
pre = cur;
stack.pop();
path.remove(path.size()-1);
SUM-=cur.val;
cur = null;
}
return res;
}
}
大概看看, 这个就是用Stack来写也不难, 反正也不用控制order;
submission最优解: 3(38):
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null){
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
dfs(root, sum, result, list);
return result;
}
private void dfs(TreeNode node, int sum, List<List<Integer>> result, List<Integer> list){
list.add(node.val);
sum = sum - node.val;
if(node.left == null && node.right == null && sum == 0){
result.add(new ArrayList<>(list));
}
if(node.left != null){
dfs(node.left, sum , result, list);
}
if(node.right != null){
dfs(node.right, sum, result, list);
}
sum = sum + node.val;
list.remove(list.size() - 1);
}
}
backtracking最后还是快一些;
Problem Description
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]
]
Difficulty:Medium
Total Accepted:155.1K
Total Submissions:440.3K
Contributor:LeetCode
Companies
bloomberg
Related Topics
treedepth-first search
Similar Questions
Path SumBinary Tree PathsPath Sum IIIPath Sum IV