Tree UVA - 548 (DFS+建立二叉树)
程序员文章站
2022-06-09 20:22:29
...
解题思路:
根据中序后序建立二叉树,利用DFS便利每条路径的和
这里要注意输入:
bool read_List(int* a){
string line;
if(!getline(cin,line)) return false; //如果为空,则直接退出
stringstream ss(line); //化为stream流
int x;
n = 0;
while(ss >> x) a[n++] = x;
return n > 0;
}
我们可以在读入字符串后,利用stringstream去除空格,把字符串中的数字全部读出来
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
const int MAXN = 10010;
int midArr[MAXN],postArr[MAXN];
int n;
int leastNode = 0x3fffffff;
int minRoute = 0x3fffffff;
vector<int> routes;
bool flag = true;
bool read_List(int* a){
string line;
if(!getline(cin,line)) return false; //如果为空,则直接退出
stringstream ss(line); //化为stream流
int x;
n = 0;
while(ss >> x) a[n++] = x;
return n > 0;
}
struct stNode{
int stData;
stNode *lchild,*rchild;
stNode(int _value){
stData = _value;
lchild = rchild = nullptr;
}
};
//DFSfind
void DFSfind(stNode* sroot){
if(sroot->lchild == nullptr && sroot->rchild == nullptr){
routes.push_back(sroot->stData);
//求和
int tempSum = 0;
for(int k = 0; k < routes.size();++k){
tempSum += routes[k]; //加上tempSum的和
}
if(tempSum == minRoute){
if(sroot->stData < leastNode){
leastNode = sroot->stData;
}
}
else if(tempSum < minRoute){
minRoute = tempSum;
leastNode = sroot->stData;
}
routes.pop_back();
}
if(sroot->lchild != nullptr){
routes.push_back(sroot->stData);
DFSfind(sroot->lchild);
routes.pop_back(); //出队
}
if(sroot->rchild != nullptr){
routes.push_back(sroot->stData);
DFSfind(sroot->rchild);
routes.pop_back();
}
}
stNode* buildTree(int posL,int posR,int inL,int inR){
if(posL > posR) return nullptr;
int curposRoot = postArr[posR];
int curInroot = -1;
int k;
for(int i = inL;i <= inR;++i){
if(midArr[i] == curposRoot){
curInroot = midArr[i];
k = i;
break;
}
}
if(curInroot == -1) return nullptr;
stNode* croot = new stNode(curposRoot);
int numK = k - inL;
croot->lchild = buildTree(posL,posL+numK-1,inL,k-1); //向左
croot->rchild = buildTree(posL+numK,posR-1,k+1,inR); //向右
return croot; //返回头结点
}
int main(){
while(read_List(midArr)){
read_List(postArr);
leastNode = 0x3fffffff;
minRoute = 0x3fffffff;
routes.clear();
stNode* troot = buildTree(0,n-1,0,n-1); //建树
DFSfind(troot);
cout<<leastNode<<endl;
}
system("PAUSE");
return 0;
}
上一篇: PAT求单链表结点的阶乘和
推荐阅读
-
Tree UVA - 548 (DFS+建立二叉树)
-
Uva548(二叉树通过中序和后序遍历数据创建树)
-
【代码超详解】UVA 548 Tree 树(二叉树、DFS)
-
二叉树遍历(前序、中序、后序) UVA 548 Tree
-
数据结构-树与二叉树-二叉树的递归遍历(Tree UVA - 548||Not so Mobile UVA - 839||The Falling Leaves UVA - 699)
-
Uva548 Tree(十多次RE自闭)
-
UVA 548 根据中序和后序建立二叉树并求根到叶的最短路
-
POJ2255 ZOJ1944 UVA536 Tree Recovery【二叉树遍历】
-
Tree Recovery poj2255(前序中序遍历建立二叉树)
-
UVA 548 - Tree(树)