1、二叉树的路径和
https://www.lintcode.com/problem/binary-tree-path-sum/description
描述
给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。
一个有效的路径，指的是从根节点到叶节点的路径。
您在真实的面试中是否遇到过这个题？ 是
题目纠错
样例
输入:
{1,2,4,2,3}
5
输出: [[1, 2, 2],[1, 4]]
说明:
这棵树如下图所示：
1
/
2 4
/
2 3
对于目标总和为5，很显然1 + 2 + 2 = 1 + 4 = 5
class Solution {
public:
/*
* @param root: the root of binary tree
* @param target: An integer
* @return: all valid paths
*/
vector<vector<int>> binaryTreePathSum(TreeNode * root, int target) {
// write your code here
vector<vector<int>> vecRes;
vector<int> vec;
pathSum(vecRes, vec, root, target);
return vecRes;
}
void pathSum(vector<vector<int>> &vecRes, vector<int> &vec, TreeNode * node, int target) {
if (NULL == node) {
return;
}
vec.push_back(node->val);
if (NULL == node->left && NULL == node->right) {
int sum = accumulate(vec.begin(), vec.end(), 0);
if (sum == target) {
vector<int> newVec(vec);
vecRes.push_back(newVec);
}
}
if (NULL != node->left) {
pathSum(vecRes, vec, node->left, target);
vec.pop_back();
}
if (NULL != node->right) {
pathSum(vecRes, vec, node->right, target);
vec.pop_back();
}
}
};
2、二叉树的路径和II
https://www.lintcode.com/problem/binary-tree-path-sum-ii/description
描述
给一棵二叉树和一个目标值，设计一个算法找到二叉树上的和为该目标值的所有路径。路径可以从任何节点出发和结束，但是需要是一条一直往下走的路线。也就是说，路径上的节点的层级是逐个递增的。
样例
输入:
{1,2,3,4,#,2}
6
输出:
[
[2, 4],
[1, 3, 2]
]
解释:
这棵二叉树如图所示：
1
/
2 3
/ /
4 2
对于给定目标值6, 很显然有 2 + 4 = 6 和 1 + 3 + 2 = 6 两条路径。
解题思路：
从根结点开始往下遍历二叉树，每遍历一个结点，就把当前结点当作终点，然后回头看当前路径是否有满足条件的子路径
class Solution {
public:
/*
* @param root: the root of binary tree
* @param target: An integer
* @return: all valid paths
*/
vector<vector<int>> binaryTreePathSum2(TreeNode * root, int target) {
// write your code here
vector<vector<int>> vecRes;
vector<int> vec;
pathSum(vecRes, vec, root, target);
return vecRes;
}
void pathSum(vector<vector<int>> &vecRes, vector<int> &vec, TreeNode * node, int target) {
if (NULL == node) {
return;
}
vec.push_back(node->val);
int sum = 0;
for (int i = vec.size() - 1; i >= 0; i--) {
sum += vec[i];
if (sum == target) {
vector<int> newVec(vec.begin() + i, vec.end());
vecRes.push_back(newVec);
}
}
if (NULL != node->left) {
pathSum(vecRes, vec, node->left, target);
vec.pop_back();
}
if (NULL != node->right) {
pathSum(vecRes, vec, node->right, target);
vec.pop_back();
}
}
};
