1030 求先序排列

难度：普及-（普及）

题目类型：字符串/树形结构

提交次数：1

涉及知识：二叉树

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

代码：

 1 #include<iostream>
 2 using namespace std;
 3 string x, y;
 4 //表示输出一个中序排列为x[l1]-x[r1]，后续排列为y[l2]-y[r2]的二叉树的前序排列
 5 void tree(int l1, int r1, int l2, int r2){ 
 6     if(l1 > r1) return;
 7     if(l1 == r1){
 8         cout<<x[l1];
 9         return;
10     }
11     else{
12         cout<<y[r2];
13         int k = x.find(y[r2]);
14         tree(l1, k-1, l2, l2+k-1-l1);
15         tree(k+1, r1, l2+k-l1, r2-1);
16     }
17 }
18 int main(){
19     int len;
20     cin>>x>>y;
21      len = x.length();
22      tree(0, len-1, 0, len-1);
23     return 0;
24 }

备注：

老题，第一次做的时候随便抄了抄，也没怎么看懂。这一次经过我的深思熟虑，嗯，tree(int l1, int r1, int l2, int r2)表示输出一个中序排列为x[l1]-x[r1]，后续排列为y[l2]-y[r2]的二叉树的前序排列。14、15行的参数就好算了。有一个小问题，就是14、15行前不能加return啊！加了以后不就只能返回左子树了吗。。太愚蠢了。。