首页 > 其他 > 详细

剑指offer---二叉树中和为某一值的路径

时间:2018-10-21 22:17:35      阅读:133      评论:0      收藏:0      [点我收藏+]

题目:二叉树中和为某一值的路径

要求:输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
13 
14     }
15 };

 

解题代码:

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
13         vector<vector<int> > res;
14         vector<int> path;
15         int currentSum = 0;
16         if(root == NULL)
17             return res;
18         search(root, expectNumber, path, res, currentSum);
19         return res;
20     }
21 
22     void search(TreeNode* proot, int expectNumber, vector<int> &path,
23             vector<vector<int> > &res, int currentSum){
24 
25         currentSum += proot->val;
26         path.push_back(proot->val);
27 
28         bool isLeaf = proot->left == NULL && proot->right == NULL;
29         // 
30         if(currentSum == expectNumber && isLeaf){
31             res.push_back(path);
32             path.pop_back();
33             return ;
34         }
35         //
36         if(proot->left != NULL)
37             search(proot->left, expectNumber, path, res, currentSum);
38         if(proot->right != NULL)
39             search(proot->right, expectNumber, path, res, currentSum);
40         path.pop_back();
41     }
42 };

 

时间有限,先把答案放到这里,有时间再过来添加详细内容。

剑指offer---二叉树中和为某一值的路径

原文:https://www.cnblogs.com/iwangzhengchao/p/9827252.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!