UVA536 二叉树重建 Tree Recovery

简介: UVA536 二叉树重建 Tree Recovery

题意

输入一棵二叉树的先序遍历和中序遍历序列,输出它的后序遍历序列。

输入

DBACEGF ABCDEFG
BCAD CBAD

输出

ACBFGED
CDAB

思路:我们可以通过二叉树的先序和中序可以推出后序节点.先序得根,中序分左右,通过递归便可输出后序节点.

此题中只是输出后序,没有必要存储起来

#include<bits/stdc++.h>
using namespace std;
string preorder,inorder;
void solve(string pre,string in){
  int index = in.find(pre[0]);
  if(pre==""){//递归结束条件 
    return;
  }
  solve(pre.substr(1,index),in.substr(0,index)) ;
  solve(pre.substr(index+1),in.substr(index+1));
  cout<<pre[0];
}
int main()
{
  while(cin>>preorder>>inorder){
    solve(preorder,inorder);
    cout<<endl;
  }
  return 0;
}

由于上面是参数传递的是字符串,中间用到了substr函数,在处理时效率较低,所以我们可以把参数改为传递索引,这样效率就大大提高了.

参考代码2

#include<bits/stdc++.h>
using namespace std;
string preorder,inorder;
void solve(int pre,int in,int len){
  if(len <= 0){//结束条件 
    return;
  }
  int index = inorder.find(preorder[pre])-in;//根节点在中序的位置索引 -- 字符串起始索引就是根节点左右子树的结点数. 
  solve(pre+1,in,index);
  solve(pre+index+1,in+index+1,len-index-1);//左右子树的节点数不一定相等,所以得用总长度-左子树结点的个数  要注意索引是从0开始的.所以最后要-1 
  cout<<preorder[pre]; 
} 
int main()
{
  while(cin>>preorder>>inorder){
    int len = preorder.size();
    solve(0,0,len);//分别指代 先序起始索引,中序起始索引,  长度 
    cout<<endl;
  }
  return 0;
}

注:substr(index,pos),从index开始截取pos个字符.如果第二个参数不写,默认截取到最后.

目录
打赏
0
0
0
0
29
分享
相关文章
uva 536 - Tree Recovery
点击打开链接uva 536 思路: 二叉树 分析: 1 题目给定前序序列和中序序列,要求二叉树的后序序列 2 建好二叉树之和直接遍历输出即可,裸题 代码: #include #include #include #include usi...
856 0
uva 548 Tree
点击打开链接uva 548 思路: 二叉树 分析: 1 题目给定一棵二叉树的中序序列和后序序列求这个二叉树里面,根节点到叶子节点的最短路径的叶子节点的值,如果有多条路径输出最小的叶子节点 2 题目说最多有10000个节点,但是由于题目所说...
1169 0
uva 112 Tree Summing
点击打开链接 题目意思:给定一个字符串,把字符串里面的数字建成一颗树,数字有可能是负号,所以这一题其实有很多可以学的,比如怎样输入会有多行,还有怎么建立一颗树,等等。
794 0
Tree Recovery
Tree Recovery
55 0
[LeetCode] Merge Two Binary Trees 合并二叉树
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
1281 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等