#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <sstream>using namespace std;/*問題:Given a binary tree containing digits from 0-9 only, each root-to-leaf path could rePResent a number.An example is the root-to-leaf path 1->2->3 which represents the number 123.Find the total sum of all root-to-leaf numbers.For example,    1   / /  2   3The root-to-leaf path 1->2 represents the number 12.The root-to-leaf path 1->3 represents the number 13.Return the sum = 12 + 13 = 25.分析：此題實際上就是要求出從根節點到葉子結點的所有路徑，將各個路徑上代表的數字求和。從根節點遍歷到葉子結點，可以用遞歸。如果當前結點為空，直接返回；如果當前結點為葉子結點，說明已經到達末尾，將葉子結點的值壓入結果，將結果存入到結果集；其余情況表明結點是非葉子節點，需要遞歸遍歷左子樹，設返回的結果leftStrs(應該是一個集合)，遞歸遍歷右子樹，返回的結果為rightStrs，則當前結點返回: 將sCur 與 sLeft集合中的每個字符串 組成新的字符串集合lefts,將sCur 與 rightStrs中每個字符串組成的新的字符串集合rights將lefts和rights合并成新的結果集results返回遍歷results中每個元素求和    1   / /  2   34  5 6  7輸入:3(二叉樹結點個數)1 2 3(每個結點的值)51 2 3 4 5 N N1121 2輸出:25262112關鍵:1 一種更簡單的方法，高位在頂部：可以采用 10 * n + val的形式將左右子樹的和累加并返回。由于高位已經傳入，每次是高位 * 10然后加上當前位，保證了正確性2 方法2：如果當前是非葉子節點，需要遞歸遍歷左子樹，設返回的結果leftStrs(應該是一個集合)，遞歸遍歷右子樹，返回的結果為rightStrs，則當前結點返回: 將sCur 與 sLeft集合中的每個字符串 組成新的字符串集合lefts,將sCur 與 rightStrs中每個字符串組成的新的字符串集合rights*/struct TreeNode {     int val;     TreeNode *left;     TreeNode *right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:	//value是高位的值	int sum(TreeNode* root , int value)	{		if(!root)		{			return 0;		}		int curValue = value * 10 + root->val;		if(NULL == root->left && NULL == root->right)		{			return curValue;		}		int leftSum = sum(root->left , curValue);		int rightSum = sum(root->right , curValue);		return (leftSum + rightSum);	}    int sumNumbers(TreeNode* root) {		//初始的時候，高位為0        int result = sum(root , 0);		return result;	}	vector<string> dfs(TreeNode* root)	{		vector<string> results;		if(!root)		{			return results;		}		stringstream stream;		stream << root->val;		string num = stream.str();		//如果是葉子結點，直接返回該葉子結點的值		if(NULL == root->left && NULL == root->right)		{			results.push_back(num);			return results;		}		vector<string> leftResults = dfs(root->left);		vector<string> rightResults = dfs(root->right);		//拼接當前結點的值		if(!leftResults.empty())		{			int leftSize = leftResults.size();			for(int i = 0 ; i < leftSize ; i++)			{				results.push_back(num + leftResults.at(i));			}		}		if(!rightResults.empty())		{			int rightSize = rightResults.size();			for(int i = 0 ; i < rightSize ; i++)			{				results.push_back(num + rightResults.at(i));			}		}		return results;	}    int sumNumbers2(TreeNode* root) {        vector<string> results = dfs(root);		if(results.empty())		{			return 0;		}		int size = results.size();		int sum = 0;		for(int i = 0 ; i < size ; i++)		{			sum += atoi(results.at(i).c_str());		}		return sum;    }};//構建二叉樹，這里默認首個元素為二叉樹根節點，然后接下來按照作為每個結點的左右孩子的順序遍歷//這里的輸入是每個結點值為字符串，如果字符串的值為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);	}}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.sumNumbers(root);		 cout << maxSum << endl;		 deleteBinaryTree(root);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}