华为第三题practice总结

有一颗二叉树，每个节点值为非零整数，从根走到任何一个叶子节点称为一条路径，这条路径的任何一段称为路段，路段的价值等于所经过节点的值的和，请计算最大的路段价值。
                 -1
                /  \
               3    2
                     \
                     -1
                       \
                        3
最大路段价值为4.（2-> -1-> 3）


用对数器搞了一下，应该是对的


code:
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;


typedef struct TreeNode
{
	int num;
	struct  TreeNode* left;
	struct TreeNode* right;
	TreeNode() :num(0), left(NULL), right(NULL) {}
} *TREENODE;

//按照字符串构建二叉树
void Solution(string str,TREENODE* head)
{
	int left = 0;
	bool flag;
	stack<TREENODE> st;
	TREENODE p;
	while (left < str.length())
	{
		switch (str[left])
		{
		case '(':
		{
			flag = true;
			st.push(p);
			left++;
			break;
		}
		case ',':
		{
			flag = false;
			left++;
			break;
		}
		case ')':
		{
			st.pop();
			left++;
			break;
		}
		default:
		{
			if (str[left] == '-')
			{
				int start = left;
				while (str[left] != ',' && str[left] != '(' && str[left] != ')')
				{
					left++;
				}
				int num = atoi(str.substr(start+1, left - start - 1).c_str());
				 num = -num;
				p = new TreeNode();
				p->num = num;
			}
			else if(str[left]=='@')
			{
				p = NULL;
				left++;
			}
			else
			{
				int start = left;
				while (str[left] != ',' && str[left] != '(' && str[left] != ')')
				{
					left++;
				}
				int num = atoi(str.substr(start, left - start).c_str());
				p = new TreeNode();
				p->num = num;
			}
			if (*head == NULL)
				*head = p;
			else
			{
				if (flag == true)
					st.top()->left = p;
				else
					st.top()->right = p;
			}
			break;
		}
		}
	}
}

//求二叉树的所有路径
void everyroute(TREENODE head, vector<vector<int>>& res,vector<int> s)
{
	if (head->left == NULL && head->right == NULL)
	{
		s.push_back(head->num);
		res.push_back(s);
	}
	else
		s.push_back(head->num);
	if (head->left)
		everyroute(head->left, res,s);
	if (head->right)
		everyroute(head->right,res, s);
}

//其数组中最大和的子数组
int getmaxArray(vector<int> arr)
{
	int sum = arr[0];
	int n = arr[0];
	for (int i = 0; i < arr.size(); i++)
	{
		if (n > 0)
			n += arr[i];
		else
			n = arr[i];
		if (sum < n)
			sum = n;
	}
	return sum;
}


int main()
{
	//string str = "-1(3,2(0,-1))"; 
	string str= "-1(3,2(@,-1(@,3))";
	TREENODE head=NULL;
	Solution(str, &head);
	vector<int> tmp;
	vector<vector<int>> res;
	everyroute(head, res, tmp);
	long long maxsum=LLONG_MIN;
	for (int i = 0; i < res.size(); i++)
	{
		maxsum = maxsum < getmaxArray(res[i]) ? getmaxArray(res[i]) : maxsum;
	}
	cout << maxsum << endl;
	
	system("pause");
	return 0;
}