首页 > 试题广场 > 通过先序和中序数组生成后序数组
[编程题]通过先序和中序数组生成后序数组
  • 热度指数:957 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一棵二叉树的先序和中序数组,通过这两个数组直接生成正确的后序数组。

输入描述:
第一行一个整数 n,表示二叉树的大小。

第二行 n 个整数 a_i,表示二叉树的先序遍历数组。

第三行 n 个整数 b_i,表示二叉树的中序遍历数组。


输出描述:
输出一行 n 个整数表示二叉树的后序遍历数组。
示例1

输入

3
1 2 3
2 1 3

输出

2 3 1

备注:

数据保证合法
不必建树,利用递归即可。
先序NLR,中序LNR,后序LRN。
每次从a数组中得到父结点N,再去b数组中找到,分别把L和R两部分确定,接着输出N。
#include<iostream>
#include<vector>
using namespace std;
void getLRN(vector<int> a, int as, int ae, vector<int>b, int bs, int be) {
    if (as == ae) {
        cout << a[as]<<' ';
        return;
    }
    if (as > ae) return;
    int p = bs;
    while (b[p] != a[as]) p++;
    getLRN(a,as+1,p-bs+as,b,bs,p-1);
    getLRN(a,p-bs+as+1,ae,b,p+1,be);
    cout << a[as]<<' ';
}
int main() {
    int n,x;
    vector<int> a, b;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        a.push_back(x);
    }
    for (int i = 0; i < n; i++) {
        cin >> x;
        b.push_back(x);
    }
    getLRN(a,0,n-1,b,0,n-1);
    return 0;
}


发表于 2019-10-04 15:16:37 回复(0)
之前有道题是根据前中序数组构建二叉树,只要稍微改进一下代码,就可以完成后序序列的输出。
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        sc.nextLine();
        int[] pre=new int[n];
        int[] me=new int[n];
        for(int i=0;i<n;i++){
            pre[i]=sc.nextInt();
        }
        sc.nextLine();
        for(int i=0;i<n;i++){
            me[i]=sc.nextInt();
        }
        System.out.print(get(pre,me,0,n-1,0,n-1));
    }
     public static int  get(int[] pre,int[] me,int ps,int pe,int ms,int mend){
        if(ps>pe)
            return 0;
        if(ps==pe)//叶子结点
            return pre[ps];
        int index=0;
        for(;index<pre.length;index++){
            if(me[index]==pre[ps])
                break;
        }
        int length=index-ms;
        int left=get(pre,me,ps+1,ps+length,ms,index-1);//左儿子结点
         if(left!=0)
        System.out.print(left+" ");
        int right=get(pre,me,ps+length+1,pe,index+1,mend);//右儿子结点
        if(right!=0)
         System.out.print(right+" ");
      
        return pre[ps];
    }
}
发表于 2019-09-06 16:56:38 回复(0)

利用的是根据前序和中序还原树的思路求解的该问题,从右向左还原后序遍历数组

def setPos(preorder, inorder, posorder, si):
    if len(inorder)==0&nbs***bsp;si < 0:
        return si
    data = preorder[0]
    mid = inorder.index(data)
    posorder[si] = data
    si = si-1
    si = setPos(preorder[mid+1:], inorder[mid+1:], posorder, si)
    si = setPos(preorder[1:mid+1], inorder[0:mid], posorder, si)
    return si

n = int(input())
prorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))

posorder = n*['']
s = setPos(prorder, inorder, posorder, n-1)
for i in range(n):
    print(posorder[i], end=' ')

编辑于 2020-04-24 10:55:33 回复(0)
n=int(input())
preOrder=list(map(int,input().split()))
inOrder=list(map(int,input().split()))

def postOrder(preOrder,inOrder):
    if len(preOrder)==1&nbs***bsp;len(preOrder)==0:
        return preOrder
    ind=inOrder.index(preOrder[0])
    left=postOrder(preOrder[1:1+ind],inOrder[:ind])
    right=postOrder(preOrder[1+ind:],inOrder[ind+1:])
    return left+right+[preOrder[0]]
po=postOrder(preOrder,inOrder)
print(' '.join(map(str,po)))

发表于 2020-04-23 20:45:38 回复(0)
#include<bits/stdc++.h>
using namespace std;
// 无需建树,直接利用树的性质即可,递归解决
void getPost(vector<int>& pre,vector<int>& in,int pre_s,int pre_e,int in_s,int in_e,vector<int>& ans)
{
    if(pre_s>pre_e) return;
    int root = pre[pre_s];
    int index;
    for(index = in_s;index<=in_e;++index)
        if(in[index]==root)
            break;
   //   根节点
    ans.push_back(root);
    // 处理右子树
    getPost(pre,in,pre_s+(index-in_s)+1,pre_e,index+1,in_e,ans);
    // 处理左子树
    getPost(pre,in,pre_s+1,pre_s+index-in_s,in_s,index-1,ans);

}
int main()
{
    int n;
    cin>>n;
    vector<int>ans;
    vector<int>pre(n);
    vector<int>in(n);

    for(int i=0;i<n;++i)
        cin>>pre[i];
    for(int i=0;i<n;++i)
        cin>>in[i];
    getPost(pre,in,0,n-1,0,n-1,ans);
    for(int i=ans.size()-1;i!=-1;i--)
        cout<<ans[i]<<" ";

    return 0;
}
发表于 2020-02-07 12:29:03 回复(0)
参考前面同学的迭代方法来写的:
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

 void getLRN(vector<int>pre,vector<int>mid,int num){
     //根据num值来区分各种特殊情况,比如缺少某些子树
     if(num==1){
         cout<<pre[0]<<" ";
     }else if(num==2){
         if(pre[0]==mid[0])
             cout<<pre[1]<<" "<<pre[0]<<" ";
         else
             cout<<mid[0]<<" "<<mid[1]<<" ";
     }else if(num!=0){
         int root = pre[0];
         int p;
         for(p=0;p<num;p++){
             if(mid[p]==root)
                 break;
         }
         vector<int>pr1,pr2,mid1,mid2;
         if(p>0){
             pr1.assign(pre.begin()+1,pre.begin()+p+1);
             mid1.assign(mid.begin(),mid.begin()+p+1);
         }
         if(num-p-1>0){
             pr2.assign(pre.begin()+p+1,pre.begin()+num);
             mid2.assign(mid.begin()+p+1,mid.begin()+num);
         }
         getLRN(pr1,mid1,p);
         getLRN(pr2,mid2,num-p-1);
         cout<<pre[0]<<" ";
     }
 }

 int main(){
     int num;
     cin>>num;
     vector<int>pre;
     vector<int>mid;
     for(int i=0;i<num;i++){
         int data1;
         cin>>data1;
         pre.push_back(data1);
     }
     for(int j=0;j<num;j++){
         int data2;
         cin>>data2;
         mid.push_back(data2);
     }
     getLRN(pre,mid,num);
     return 0;
 }


发表于 2020-02-04 21:25:50 回复(0)
import java.util.*;

public class Main {
	static int[] preArr;
	static int[] inArr;
	static int[] arr;
	static Map<Integer, Integer> map;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        preArr = new int[n];
        inArr = new int[n];
        for(int i=0;i<n;i++){
        	preArr[i] = scanner.nextInt();
        }
         map = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
        	inArr[i] = scanner.nextInt();
        	map.put(inArr[i], i);
        }
        arr = new int[n];
        setArr(0, n-1, 0, n-1, n-1);
        for(int i=0;i<n;i++) {
        	System.out.print(arr[i]+" ");
        }
	}
	
	static  int setArr(int preStart,int preEnd,int inStart,int inEnd,int postIndex) {
		if(preStart>preEnd) return postIndex;
		
		arr[postIndex--] = preArr[preStart];
		int index = map.get(preArr[preStart]);
		
		postIndex = setArr(index - inStart + preStart +1 , preEnd, index+1,inEnd,postIndex);
		return setArr(preStart+1,index - inStart + preStart ,inStart,index-1 ,postIndex);
	}

}

发表于 2019-10-29 15:13:32 回复(0)
class Node():
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

class Tree():
    def reConstructBinaryTree(self, pre, tin):
        if len(pre) == 0:
            return
        root = Node(pre[0])
        TinIndex = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1: TinIndex+1], tin[0: TinIndex])
        root.right = self.reConstructBinaryTree(pre[TinIndex+1:], tin[TinIndex+1:])
        return root

    def PostTraversal(self, root):
        list1 = []
        if root != None:
            self.PostTraversal(root.left)
            self.PostTraversal(root.right)
            list1.append(root.val)
            print(root.val, end=' ')

if __name__ == '__main__':
    num = int(input())
    pre = list(map(int, input().split()))
    tin = list(map(int, input().split()))
    S = Tree()
    root = S.reConstructBinaryTree(pre, tin)
    S.PostTraversal(root)

发表于 2019-10-08 10:40:59 回复(0)
这道题比较蛋疼的地方也 在于树的构建。
我们使用二维数组来构建一棵树,由于树节点特殊的性质(1~10w),可以使用0作为空节点。

这样就能构建树了,构建之后用后序遍历即可
#include<bits/stdc++.h>
using namespace std;
const int N = 10001;

int n;
vector<int> preorder, inorder;
vector<vector<int>> tree(N, {0, 0});

int build(int start, int l, int r){
    if(start>=n) return 0;
    if(l>r) return 0;
    
    int node = preorder[start];
    int pos=l;
    while(pos<=r && inorder[pos]!=node) pos++;
    
    tree[node][0]=build(start+1, l, pos-1);
    tree[node][1]=build(start+pos-l+1, pos+1, r);
    return node;
}

void postorder(int root){
    if(root==0) return;
    postorder(tree[root][0]);
    postorder(tree[root][1]);
    cout<<root<<" ";
}

int main(){
    cin>>n;
    int pi;
    for(int i=0;i<n;i++){
        cin>>pi;
        preorder.push_back(pi);
    }
    for(int i=0;i<n;i++){
        cin>>pi;
        inorder.push_back(pi);
    }
    int root = build(0, 0, n-1);
    postorder(root);
    cout<<endl;
    return 0;
}


发表于 2019-08-05 20:16:17 回复(0)