-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path112-hasPathSum.h
More file actions
105 lines (83 loc) · 2.06 KB
/
112-hasPathSum.h
File metadata and controls
105 lines (83 loc) · 2.06 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#pragma once
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include "TreeDefine.h"
using namespace std;
class CSolution
{
public:
CSolution();
~CSolution();
public:
bool hasPathSum(TreeNode* root, int sum);
bool hasPathSum_stack(TreeNode* root, int sum);
vector<vector<int>> PathSum(TreeNode* root, int sum); //113
private:
void help(TreeNode* root,int sum, vector<vector<int>>& res, vector<int>& tmp);
};
CSolution::CSolution()
{
}
CSolution::~CSolution()
{
}
/*
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
*/
bool CSolution::hasPathSum(TreeNode* root, int sum)
{
if (nullptr == root)
return false;
sum -= root->val;
if(root->left == nullptr && nullptr == root->right)
return sum == 0;
if (0 == sum)
return true;
return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
}
bool CSolution::hasPathSum_stack(TreeNode* root, int sum)
{
if (root == nullptr)
return false;
stack<pair<TreeNode*, int>> stNode;
stNode.push(make_pair(root, sum - root->val));
while (!stNode.empty())
{
auto p = stNode.top();
stNode.pop();
if (p.first->left == nullptr && p.first->right == nullptr && sum == 0)
return true;
if (sum == 0)
return true;
stNode.push(make_pair(p.first->left, sum - p.first->right->val));
stNode.push(make_pair(p.first->right, sum - p.first->right->val));
}
return false;
}
//找出所有路径
std::vector<std::vector<int>> CSolution::PathSum(TreeNode* root, int sum)
{
vector<vector<int>> res;
vector<int> tmp;
//help(root, );
help(root, sum, res, tmp);
return res;
}
void CSolution::help(TreeNode* root,int sum, vector<vector<int>>& res, vector<int>& tmp)
{
if (root == nullptr) return;
tmp.push_back(root->val);
if (root->left == nullptr && root->right == nullptr && sum - root->val == 0)
{
res.push_back(tmp);
tmp.clear();
return;
}
help(root->right, sum - root->val, res, tmp);
help(root->left, sum - root->val, res, tmp);
tmp.erase(tmp.begin() + tmp.size() - 1);
}