FilesExpand file tree

 master

/

pathSum.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

98 lines (86 loc) · 2.45 KB

 master

/

pathSum.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

98 lines (86 loc) · 2.45 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

// Source : https://oj.leetcode.com/problems/path-sum/

// Author : Hao Chen

// Date : 2014-06-22

/**********************************************************************************

*

* Given a binary tree and a sum, determine if the tree has a root-to-leaf path

* such that adding up all the values along the path equals the given sum.

*

* For example:

* Given the below binary tree and sum = 22,

*

* 5

* / \

* 4 8

* / / \

* 11 13 4

* / \ \

* 7 2 1

*

* return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

*

**********************************************************************************/

#include <time.h>

/**

* Definition for binary tree

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

public:

Solution(){

srand(time(NULL));

}

bool hasPathSum(TreeNode *root, int sum) {

if (random()%2){

return hasPathSum1(root, sum);

}

return hasPathSum2(root, sum);

}

bool hasPathSum1(TreeNode *root, int sum) {

if (root==NULL) return false;

vector<TreeNode*> v;

v.push_back(root);

while(v.size()>0){

TreeNode* node = v.back();

v.pop_back();

if (node->left==NULL && node->right==NULL){

if (node->val == sum){

return true;

}

}

if (node->left){

node->left->val += node->val;

v.push_back(node->left);

}

if (node->right){

node->right->val += node->val;

v.push_back(node->right);

}

}

return false;

}

bool hasPathSum2(TreeNode *root, int sum) {

if (root==NULL) return false;

if (root->left==NULL && root->right==NULL ){

return (root->val==sum);

}

if (root->left){

root->left->val += root->val;

if (hasPathSum2(root->left, sum)){

return true;

}

}

if (root->right){

root->right->val += root->val;

if (hasPathSum2(root->right, sum)){

return true;

}

}

return false;

}

};