二叉树-路径之和
给定一个二叉树与整数sum，找出所有从根节点到叶结点的路径，这些路径上的节点值累加和为sum。
#include<vector>
struct TreeNode{
int val;
TreeNode *right;
TreeNode *left;
TreeNode(int x): val(x), left(NULL),right(NULL){}
}
class Solution{
public:
std::vector<std::vector<int>> pathSum(TreeNode *root,int sum){}
};思考
1.使用何种数据结构存储遍历路径上的节点?
使用栈的数据结构
2.在树的前序遍历时做什么?后序遍历时做什么? 3.如何判断一个节点为叶结点?当遍历到叶结点时应该做什么?
在前序遍历（每遇到一个节点）进行操作，push进栈中（vector实现 ）
算法思路
1.从根节点深度遍历二叉树，先序遍历时，将该节点值存储至path栈中(vector实 现)，使用 path_value累加节点值。 2.当遍历至叶结点时，检查path_value值是否为sum，若为sum，则将path push 进入result结果中。 3.在后序遍历时，将该节点值从path栈中弹出，path_value减去节点值。
class Solution{
public:
std::vector<std::vector<int>> pathSum(TreeNode *root,int sum){
std::vector<std::vector<int>> result;
std::vector<int> path;
int path_value = 0;
preorder(root, path_value,sum,path,result);
return result;
}
private:
void preorder(TreeNode *node,int &path_value,int sum, std::vector<int> &path,std::vector<std::vector<int>> &result){
if(!node){
return;
}
path_value += node->val;
path.push_back(node->val);
if(path_value == sum && !node->left && !node->right ){
result.push_back(path);
}
preorder(node->left, path_value,sum,path,result);
preorder(node->right, path_value,sum,path,result);
path_value -=node->val;
path.pop_back;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录