Problem
Given a binary tree, find out the maximum sum of value from root to each leaf.
find_Max(Node *root){
if (root==null)
return 0;
else
return max((find_Max(root->left), find_Max(root->right))+root->value;
}
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find out the maximum sum of value from root to each leaf.
Created Date : 27-10-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef struct binTreeNode
{
int value;
struct binTreeNode *left;
struct binTreeNode *right;
} BinTreeNode;
BinTreeNode *CreateNode(int value)
{
auto node = new BinTreeNode;
node->value = value;
node->left = nullptr;
node->right = nullptr;
return node;
}
BinTreeNode *AddNode(BinTreeNode* head, int value)
{
if(head->value > value){
if(head->left == nullptr){
BinTreeNode* node = CreateNode(value);
head->left = node;
}
else{
AddNode(head->left, value);
}
}
else{
if(head->right == nullptr){
BinTreeNode* node = CreateNode(value);
head->right = node;
}
else{
AddNode(head->right, value);
}
}
return head;
}
void PrintTree(BinTreeNode* head)
{
if(head == nullptr) return;
if(head->left != nullptr) PrintTree(head->left);
cout << head->value << endl;
if(head->right != nullptr) PrintTree(head->right);
}
BinTreeNode* CreateTree(int* arr, int len)
{
assert(arr != nullptr && len >= 1);
BinTreeNode* head = CreateNode(arr[0]);
for(int i = 1; i < len; ++i){
AddNode(head, arr[i]);
}
return head;
}
typedef struct{
BinTreeNode* node;
int sum;
} NodeSum;
int FindMaxSumToLeaf(BinTreeNode* head)
{
vector<int> results;
queue<NodeSum> nodes;
int result;
NodeSum ns;
ns.node = head;
ns.sum = head->value;
nodes.push(ns);
while(!nodes.empty()){
ns = nodes.front();
nodes.pop();
if(ns.node->left == nullptr && ns.node->right == nullptr){
results.push_back(ns.sum);
}
else{
if (ns.node->left != nullptr){
NodeSum nsl;
nsl.node = ns.node->left;
nsl.sum = ns.sum + ns.node->left->value;
nodes.push(nsl);
}
if (ns.node->right != nullptr){
NodeSum nsr;
nsr.node = ns.node->right;
nsr.sum = ns.sum + ns.node->right->value;
nodes.push(nsr);
}
}
}
return *max_element(results.begin(), results.end());
}
int main(int argc, char* argv[])
{
int arr[] = {3, 1, 2, 5, 6, 4, -1, -3, -2, 9};
BinTreeNode* head = CreateTree(arr, sizeof(arr) / sizeof(arr[0]));
cout << "Before: " << endl;
PrintTree(head);
cout << "The result : " << endl;
cout << FindMaxSumToLeaf(head) << endl;
return 0;
}
Output
Before :
-3
-2
-1
1
2
3
4
5
6
9
The result :
23
Press any key to continue . . .