首页 > 试题广场 > 通过先序和中序数组生成后序数组
[编程题]通过先序和中序数组生成后序数组
给出一棵二叉树的先序和中序数组,通过这两个数组直接生成正确的后序数组。

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

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

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


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

输入

3
1 2 3
2 1 3

输出

2 3 1

备注:

数据保证合法
之前有道题是根据前中序数组构建二叉树,只要稍微改进一下代码,就可以完成后序序列的输出。
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)
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)
不必建树,利用递归即可。
先序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)
这道题比较蛋疼的地方也 在于树的构建。
我们使用二维数组来构建一棵树,由于树节点特殊的性质(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)