2014
11-18

# LeetCode-Path Sum II[二叉树]

### 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]
]


// LeetCode, Path Sum II
// 时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
vector<vector<int> > pathSum(TreeNode *root, int sum) {
vector<vector<int> > result;
vector<int> cur; // 中间结果
pathSum(root, sum, cur, result);
return result;
}
private:
void pathSum(TreeNode *root, int gap, vector<int> &cur,
vector<vector<int> > &result) {
if (root == nullptr) return;

cur.push_back(root->val);

if (root->left == nullptr && root->right == nullptr) { // leaf
if (gap == root->val)
result.push_back(cur);
}
pathSum(root->left, gap - root->val, cur, result);
pathSum(root->right, gap - root->val, cur, result);

cur.pop_back();
}
};


Java代码:

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> lists = new ArrayList();
List<Integer> list = new ArrayList<Integer>();
pathSumRecur(root,sum,lists,list);
return lists;
}

public void pathSumRecur(TreeNode root, int sum,List<List<Integer>> lists, List<Integer> list) {
if(root == null) return;
if(root.left == null && root.right == null && root.val == sum){
List<Integer> newList = new ArrayList<Integer>(list);
}
pathSumRecur(root.left,sum-root.val,lists,list);
pathSumRecur(root.right,sum-root.val,lists,list);
list.remove(list.size()-1);
}
}

Path Sum

1. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}