数据结构-树与二叉树-二叉树的递归遍历(Tree UVA - 548||Not so Mobile UVA - 839||The Falling Leaves UVA - 699)

目录

 

二叉树的递归遍历：

Tree   UVA - 548

题目大意：

基本思路：

输入控制：

代码：

Not so Mobile UVA - 839

The Falling Leaves UVA - 699

---

二叉树的递归遍历：

         Depth-First Search(DFS):先序遍历 中序遍历 后序遍历

Tree   UVA - 548

题目大意：

         知道中序遍历和后序遍历的顺序，算出该二叉树并求出最小权值路径对应的叶结点权值(结点值为权)。如果存在相同，输出叶结点较小的。

         因为全为正整数，所以数组下标做结点即可！

如果知道前序和中序 无法确定唯一二叉树，因为无法找出子树根节点

基本思路：

         后序末尾为根节点，在对应中序中找到对应位置，分隔开前后就为左len右n-len-1子树。然后对于后序末尾之前的，前len长度为就是左子树，后面为右子树，递归如上进行下去。

         最终用dfs进行深搜出best_sum；

输入控制：

         while(scanf("%d%c",&t,&c)!=EOF){

                  int len = 1;

                  mid_order[len]=t;

                  while(c!='\n')     scanf("%d%c",&mid_order[++len],&c);

                  for(int i = 1;i <= len;i++)    cin >> post_order[i];

         }

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+50;

int lch[maxn],rch[maxn];

int mid_order[maxn],post_order[maxn];

int best_sum = 1e8;

int idx = 0;

int build(int l1,int r1,int l2,int r2){

         if(l1 > r1)  return 0;

         int root = post_order[r2];

         int p = l1;

         while(mid_order[p] != root)        p++;

         int len = p-l1;

         lch[root] = build(l1,p-1,l2,l2+len-1);

         rch[root] = build(p+1,r1,l2+len,r2-1);

         return root;

}

void dfs(int u,int sum){

         if(lch[u] == 0&&rch[u] == 0){

                  if(sum+u < best_sum||((sum+u == best_sum)&&(idx > u))){

                          idx = u;best_sum = sum+u;

                  }

                  return ;

         }

         if(lch[u])    dfs(lch[u],sum+u);

         if(rch[u])   dfs(rch[u],sum+u);

}

int main(){

         cin.tie(0);cout.tie(0);

         int t;

         char c;

         while(scanf("%d%c",&t,&c)!=EOF){

                  int len = 1;

                  mid_order[len]=t;

                  while(c!='\n')     scanf("%d%c",&mid_order[++len],&c);

                  for(int i = 1;i <= len;i++)    cin >> post_order[i];

                  best_sum = 1e8;idx=0;

                  build(1,len,1,len);

                  dfs(post_order[len],0);

                  cout<<idx<<endl;

         }

         return 0;

}

Not so Mobile UVA - 839

#include<bits/stdc++.h>



using namespace std;

typedef long long ll;

const int maxn = 1e6+50;

bool isequal(int& w){

         int wl,wr,dl,dr;

         cin>>wl>>dl>>wr>>dr;

         bool l = true,r=true;

         if(wl==0)   l=isequal(wl);

         if(wr==0)  r=isequal(wr);

         w = wl+wr;

         return l&&r&&(wl*dl==wr*dr);

}

int main(){

         int t,w=0;

         cin >> t;

         for(int i = 0;i < t;i++){

                  printf("%s",isequal(w)?"YES":"NO");

                  printf("%s",i==t-1?"\n":"\n\n");

         }

         return 0;

}

The Falling Leaves UVA - 699

#include<bits/stdc++.h>



using namespace std;

typedef long long ll;

const int maxn = 1e6+50;

map<int,int>cnt;

void solve(int pos){

         int v;

         scanf("%d",&v);

         if(v != -1){

                  cnt[pos]+=v;

                  solve(pos-1);

                  solve(pos+1);

         }

}

int main(){

         int t;

         char c;

         for(int i = 1;;i++){

                  cnt.clear();

                  solve(0);

                  if(cnt.empty())   break;

                  printf("Case %d:\n",i);

                  for(map<int,int>::iterator it = cnt.begin();it != cnt.end();it++){

                          cout << it->second;

                          if(it->first == cnt.rbegin()->first) puts("");

                          else cout<<' ';

                  }

                  printf("\n");

         }

         return 0;

}