#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <queue>#include <sstream>using namespace std;/*問題:Given a binary tree, find the maximum path sum.For this PRoblem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.For example:Given the below binary tree,       1      / /     2   3Return 6.分析：從二叉樹的任意結點開始到某個結點截止的路徑，計算路徑的最大和。這個好像是程序員面試結點的題目。一種方法是：維護一個自底向上的到當前結點的路徑和，比如結點:12是葉節點，對應截止到結點12的路徑和為12；結點-2，路徑和: 12 - 2=10,結點2：需要從左孩子4的截止路徑和和-2的路徑和中選擇一個較大的，如果兩者中較大的都小于0，那么就使路徑和為本身，這里為12.回溯到1，為13。對于葉節點1，路徑和:1，-3：路徑和-2葉節點-1：路徑和為-1.2：路徑和2,3路徑和為：5對于根節點1，左邊路徑和為:12,右邊路徑和為5，選擇：左邊較大變成:12 , 1 ,5根據最大子數組應該全部鏈接，最終結果為18如果題目是求從任意結點到根節點的最大路徑和，那么剛才所講的方法是可以的，因為每次遇到當前結點，只需要計算出當前結點左邊路徑和leftSum,右邊路徑和rightSum,然后選取最終tempMax = max(leftSum , rightSum);maxSum = tempMax > 0 ? (tempMax + value) : value;其中value是當前結點的值關鍵:1 但是題目現在是求任意結點到任意結點的最大路徑和，決策情況變了：1】要么是從當前結點或者當前結點的左右孩子結點中選擇一個最大的連接起來并提供給父節點使用2】要么是以當前結點來連接左邊和右邊的子樹，作為最終的結果   設左子樹路徑和為leftSum,右子樹路徑和為rightSum,當前結點的值為value，提供給上層的結點值為curSum初始結果result = INT_MIN, tempMax設minNum=min(leftSum , rightSum),maxNum=max(leftSum , rightSum)如果左右子樹的路徑和都小于0，僅僅提供當前結點給父節點使用1.1】leftSum < 0 && rightSum < 0,curSum=value , tempMax = value,  如果左子樹路徑和大于0，右子樹路徑和<0，左子樹+當前結點的和提供給父節點使用1.2】leftSum > 0 && rightSum < 0,curSum= leftSum + value, tempMax = max(leftSum , leftSum + value),如果右子樹路徑和>0,左子樹路徑和<0，右子樹+當前結點提供給父節點使用1.3】leftSum < 0 && rightSum > 0,curSum = rightSum + value, tempMax = max(rightSum , rightSum + value),如果左子樹路徑和>0，右子樹路徑和>0，設較小路徑和為min,較大路徑和為max1.4】leftSum > 0 && rightSum > 0,curSum = maxNum + value， tempMax=max(leftSum , rightSum , leftSum + value + rightSum)   result = max(result , tempMax);問題的關鍵是如何自底向上，通過遞歸遍歷到葉子結點，就返回結點的值本身；如果是非葉子結點：返回左右子樹中的較大值 + 當前結點值本身，作為路徑和，并更新result2 追憶葉子結點路徑和為本身，葉子結點也需要和最大結果比較if(NULL == root->left && NULL == root->right){	_result = max(_result , root->val);//也需要和葉子結點比較，如果只有一個根節點	return root->val;}舉例:其中N表示空結點			1		2		   3 	  4   -2     -3   2	 N N  N 12  1  N N -1輸入:151 2 3  4 -2 -3 2 N N N 12 1 N N -1112-12 13輸出:18113關鍵:1 */struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:	int dfs(TreeNode* root)	{		//空結點路徑和為0		if(!root)		{			return 0;		}		//葉子結點路徑和為本身，葉子結點也需要和最大結果比較		if(NULL == root->left && NULL == root->right)		{			_result = max(_result , root->val);//也需要和葉子結點比較，如果只有一個根節點			return root->val;		}		//遞歸遍歷左子樹和右子樹路徑和		int leftSum = dfs(root->left);		int rightSum = dfs(root->right);		int maxNum = max(leftSum , rightSum);		int curSum = INT_MIN;		//左右子樹路徑和都小于0，返回當前結點值為本身		if(leftSum < 0 && rightSum < 0)		{			curSum = root->val;			_result = max(_result , curSum);		}		//左右子樹都大于0，		else if(leftSum > 0 && rightSum > 0)		{			curSum = maxNum + root->val;			//最大值可能是直接以當前點連接左右子樹的結果			_result = max(_result , leftSum + root->val + rightSum);		}		//左右子樹中有1個大于0，		else		{			curSum = maxNum + root->val;			_result = max(_result , curSum);		}		return curSum;	}    int maxPathSum(TreeNode* root) {        _result = INT_MIN;		dfs(root);		return _result;    }public:	int _result;};//構建二叉樹，這里默認首個元素為二叉樹根節點，然后接下來按照作為每個結點的左右孩子的順序遍歷//這里的輸入是每個結點值為字符串，如果字符串的值為NULL表示當前結點為空TreeNode* buildBinaryTree(vector<string>& nums){	if(nums.empty())	{		return NULL;	}	int size = nums.size();	int j = 0;	//結點i的孩子結點是2i,2i+1	vector<TreeNode*> nodes;	int value;	for(int i = 0 ; i < size ; i++)	{		//如果當前結點為空結點，自然其沒有左右孩子結點		if("N" == nums.at(i))		{			nodes.push_back(NULL);			continue;		}		value = atoi(nums.at(i).c_str());		TreeNode* node = new TreeNode(value);		nodes.push_back(node);	}	//設定孩子結點指向,各個結點都設置好了，如果但錢為空結點，就不進行指向	for(int i = 1 ; i <= size ; i++)	{		if(NULL == nodes.at(i-1))		{			continue;		}		if(2 * i <= size)		{			nodes.at(i-1)->left = nodes.at(2*i - 1);		}		if(2*i + 1 <= size)		{			nodes.at(i-1)->right = nodes.at(2*i);		}	}	//設定完了之后，返回根節點	return nodes.at(0);}void deleteBinaryTree(TreeNode* root){	if(!root)	{		return;	}	if(NULL == root->left && NULL == root->right)	{		delete root;		root = NULL;	}	if(root)	{		deleteBinaryTree(root->left);		deleteBinaryTree(root->right);	}}//層序遍歷vector<vector<string>> levelOrder(TreeNode* root) {	vector<vector<string>> results;    if(NULL == root)	{		return results;	}	queue<TreeNode*> nodes;	nodes.push(root);	int size = 1;	int nextSize = 0;	vector<string> result;	TreeNode* node = NULL;	while(!nodes.empty())	{		node = nodes.front();		nodes.pop();		if(node)		{			stringstream stream;			stream << node->val;			result.push_back(stream.str());		}		else		{			result.push_back("N");//表示空結點		}		if(node->left)		{			nodes.push(node->left);			nextSize += 1;		}		if(node->right)		{			nodes.push(node->right);			nextSize += 1;		}		size--;		if(0 == size)		{			size = nextSize;			nextSize = 0;			vector<string> tempResult(result);			results.push_back(tempResult);			result.clear();		}	}	return results;}void print(vector<vector<string>>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	int len;	for(int i = 0 ; i < size ; i++)	{		len = result.at(i).size();		for(int j = 0 ; j < len ; j++)		{			cout << result.at(i).at(j) << " " ;		}		cout << endl;	}	cout << endl;}void process(){	 vector<string> nums;	 string value;	 int num;	 Solution solution;	 vector<vector<string> > result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 TreeNode* root = buildBinaryTree(nums);		 int maxSum = solution.maxPathSum(root);		 cout << maxSum << endl;		 //打印二叉樹中序結點值		 //result = levelOrder(root);		 //print(result);		 deleteBinaryTree(root);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}