首页 > 代码库 > 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]]
这道二叉树路径之和在之前的基础上又需要找出路径 (可以参见我之前的博客 http://www.cnblogs.com/grandyang/p/4036961.html)，但是基本思想都一样，还是需要用广度优先搜索DFS，只不过数据结构相对复杂一点，需要用到二维的vector，而且每当DFS搜索到新节点时，都要保存该节点。而且每当找出一条路径之后，都将这个保存为一维vector的路径保存到最终结果二位vector中。并且，每当DFS搜索到子节点，发现不是路径和时，返回上一个结点时，需要把该节点从一维vector中移除。代码如下：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int> > res; if (root == NULL) return res; vector<int> onePath; onePath.push_back(root->val); pathSum_DFS(root, sum, onePath, res); return res; } void pathSum_DFS(TreeNode *root, int sum, vector<int> &onePath, vector<vector<int> > &res) { if (root->left == NULL && root->right == NULL && root->val == sum) { res.push_back(onePath); return; } if (root->left) { onePath.push_back(root->left->val); pathSum_DFS(root->left, sum - root->val, onePath, res); onePath.pop_back(); } if (root->right) { onePath.push_back(root->right->val); pathSum_DFS(root->right, sum - root->val, onePath, res); onePath.pop_back(); } }};
Path Sum II 二叉树路径之和之二
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。