首页 > 代码库 > 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]]
Hide Tags
Tree Depth-first Search/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {private: vector<vector<int> > paths;public: void dfs(TreeNode *node,int sum,int csum,vector<int> onePath){ //a能为引用 if(node==NULL) return; if(node->left==NULL && node->right==NULL){ if(node->val+csum==sum){ onePath.push_back(node->val); paths.push_back(onePath); } return; } onePath.push_back(node->val); dfs(node->left,sum,csum+node->val,onePath); dfs(node->right,sum,csum+node->val,onePath); } vector<vector<int> > pathSum(TreeNode *root, int sum) { paths.clear(); vector<int> onePath; dfs(root,sum,0,onePath); return paths; }};
Path Sum II深度优先找路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。