C-data-structure-/void_Problem_3.cpp at main · Abdullah-Tahir/C-data-structure- · GitHub

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
#include <iostream>
#include<climits>

using namespace std;

struct Node {
	int data;
	Node* left, * right;
};


Node* getNode(int data)
{

	Node* temp = new Node;

	temp->data = data;
	temp->left = temp->right = NULL;
	return temp;
}

void helper(Node* root, int sum,
	int len, int& maxLen, int& maxSum)
{

	if (!root) {

		if (maxLen < len) {
			maxLen = len;
			maxSum = sum;
		}
		else if (maxLen == len && maxSum < sum)
			maxSum = sum;
		return;
	}


	helper(root->left, sum + root->data,
		len + 1, maxLen, maxSum);

	helper(root->right, sum + root->data,
		len + 1, maxLen, maxSum);
}

int maxPathSum(Node* root)
{

	if (!root)
		return 0;

	int maxSum = INT_MIN, maxLen = 0;
	helper(root, 0, 0, maxLen, maxSum);

	return maxSum + 1;
}


int main()
{

	Node* root = getNode(-10);


	root->right = getNode(9);

	root->right->right = getNode(20);
	root->right->right->left = getNode(15);
	root->right->right->left->left = getNode(7);

	cout << "Sum = "
		<< maxPathSum(root);

	return 0;
}