uva 548

本文主要是介绍uva 548，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你一个树的中序。后序遍历，让你找到前序遍历过程中，总和最大的一条路的叶节点的值。。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 10005 ;int inOrder[MAXN],postOrder[MAXN],nIndex;
class Node
{public:int data;Node *left;Node *right;
};
int nodeIndex;
Node node[MAXN];
vector<int>result;
vector<Node*>pResult;
bool flag;
int ans;inline Node* NewNode()
{node[nodeIndex].left = NULL;node[nodeIndex].right = NULL;return &node[nodeIndex++];
}inline void input()
{nIndex = 1 ;while (getchar() != '\n')scanf("%d",&inOrder[nIndex++]);for (int i = 0 ; i < nIndex ; i++)scanf("%d",&postOrder[i]);
}Node* build(int *mid,int *post,int len)
{if (len == 0 )return NULL;int i = len - 1 ;while (post[len-1] != mid[i])i--;Node *h = NewNode();h->data = post[len-1];h->left = build(mid,post,i);h->right = build(mid+1+i,post+i,len-i-1);return h;
}void dfs(Node *root ,int n)
{if(root->left == NULL && root->right == NULL){result.push_back(n+root->data);pResult.push_back(root);return ;}if(root->left) dfs(root->left,n+root->data);if(root->right) dfs(root->right,n+root->data);
}int main()
{while (scanf("%d",&inOrder[0]) != EOF){input();nodeIndex = 0 ;Node *root = build(inOrder,postOrder,nIndex);result.clear();pResult.clear();dfs(root,0);int Min = 0 ;for (int i = 1 ; i < result.size() ; i++)if (result[i] < result[Min])Min = i ;printf("%d\n",pResult[Min]->data);}return 0;}

这篇关于uva 548的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---