树的不同形态

/**
*1.利用层次遍历和中序遍历还原数组，我采用的是递归的方式，同时在递归的过程中判断记录叶子节点
*2.先序遍历
*3.后序遍历
*说明：中序遍历的根节点左边是左子树，右边是右子树，在层次遍历中根节点是第一个，然后把左子树的层次遍历和右子树的此次遍历提取出来进行递归
*/

	import java.util.*;

public class Main {
    public static StringBuffer sb1=new StringBuffer();
    public static StringBuffer sb2=new StringBuffer();
    public static StringBuffer sb3=new StringBuffer();
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        String str1=scan.nextLine();
        String str2=scan.nextLine();
        String[] s1=str1.split(" ");
        TreeNode root=xun(s1,str2);
        preOrder(root);
        postOrder(root);
        System.out.println(sb1.toString().trim());
        System.out.println(sb2.toString().trim());
        System.out.println(sb3.toString().trim());
    }
    public static TreeNode xun(String[] a,String b){
        if(b.length()==0) return null;
        int index=0;
        String[] s2=b.split(" ");
        int len=s2.length;
        TreeNode temp=new TreeNode(a[0]);
        for(;index<len;index++){
            if(a[0].equals(s2[index])) break;
        }
        ArrayList<String> list1=new ArrayList(Arrays.asList(a));
        ArrayList<String> list2=new ArrayList(Arrays.asList(a));
        for(int i=0;i<=index;i++)
            list1.remove(s2[i]);
        for(int i=index;i<len;i++)
            list2.remove(s2[i]);
        temp.left=xun(list2.toArray(new String[list1.size()]),b.substring(0,b.indexOf(s2[index])));
        if(index==len-1)
            temp.right=null;
        else
            temp.right=xun(list1.toArray(new String[list2.size()]),b.substring(b.indexOf(s2[index+1])));
        if(temp.left==null&&temp.right==null) sb1.append(temp.val+" ");
        return temp;
    }
    public static void preOrder(TreeNode root){
        if(root!=null){
            sb2.append(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    public static void postOrder(TreeNode root){
        if(root!=null){
            postOrder(root.left);
            postOrder(root.right);
            sb3.append(root.val+" ");
        }
    }
}
class TreeNode{
    public String val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(String val){
        this.val=val;
        this.left=null;
        this.right=null;
    }
}
	

		
	




	

#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left,*right;
    TreeNode(int v):val(v),left(nullptr),right(nullptr){}
};

TreeNode* createTree(vector<int>inorder,vector<int>seq,int begin,int end)
{
    if(seq.size()<=0) return nullptr;
    TreeNode *root=new TreeNode(seq[0]);
    vector<int>left;
    vector<int>right;
    int k;
    for(k=begin;k<=end;++k)
        if(inorder[k]==seq[0])
        break;
    bool isleft;
    for(int i=1;i<seq.size();++i)
    {
        isleft=false;
        for(int j=begin;j<k;++j)
        {
            if(seq[i]==inorder[j])
            {
                isleft=true;
                break;
            }
        }
        if(isleft)
            left.push_back(seq[i]);
        else right.push_back(seq[i]);
    }
    root->left=createTree(inorder,left,begin,k-1);
    root->right=createTree(inorder,right,k+1,end);
    return root;
}

void preorder(TreeNode *ptr,vector<int>&pre)
{
    if(ptr!=nullptr)
    {
        pre.push_back(ptr->val);
        preorder(ptr->left,pre);
        preorder(ptr->right,pre);
    }
}

void postorder(TreeNode *ptr,vector<int>&post)
{
    if(ptr!=nullptr)
    {
        postorder(ptr->left,post);
        postorder(ptr->right,post);
        post.push_back(ptr->val);
    }
}
void getleafNode(TreeNode *ptr,vector<int>&leaf)
{
    if(ptr==nullptr) return ;
    if(ptr!=nullptr&&ptr->left==nullptr&&ptr->right==nullptr)
        {
            leaf.push_back(ptr->val);
            return ;
        }
    getleafNode(ptr->left,leaf);
    getleafNode(ptr->right,leaf);
    return ;
}
int main()
{
    int n;
    char *str=new char[100];
    vector<int>inorder;
    vector<int>seq;
    cin.getline(str,100);
    char *temp;
    temp=strtok(str," ");
    while(temp)
    {
        sscanf(temp,"%d",&n);
        seq.push_back(n);
        temp=strtok(NULL," ");
    }
    cin.getline(str,100);
    temp=strtok(str," ");
    while(temp)
    {
        sscanf(temp,"%d",&n);
        inorder.push_back(n);
        temp=strtok(NULL," ");
    }
    TreeNode *root=createTree(inorder,seq,0,inorder.size()-1);
    vector<int>pre,post,leaf;
    preorder(root,pre);
    postorder(root,post);
    getleafNode(root,leaf);
    for(int i=0;i<leaf.size();++i)
        cout<<leaf[i]<<" ";
    cout<<endl;
    for(int i=0;i<pre.size();++i)
        cout<<pre[i]<<" ";
    cout<<endl;
    for(int i=0;i<post.size();++i)
        cout<<post[i]<<" ";
    cout<<endl;
    return 0;
}

	

class TreeNode(object):
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x
 
 
class Solution(object):
    def __init__(self):
        self.leaf = []
 
    def creatTree(self, bfsorder, inorder):
        """
        从中序遍历找出左右子树，然后再从序列层次遍历中找出左右子树序列，重建二叉树
        :param bfsorder:
        :param inorder:
        :return:
        """
        if len(bfsorder) < 1:
            return
        if len(bfsorder) == 1 and bfsorder[0] not in self.leaf:
            self.leaf.append(bfsorder[0])
            # print(self.leaf)
        root = TreeNode(bfsorder[0])
        root_index = inorder.index(root.val)  # 根节点在中序遍历的索引
        left_in = inorder[:root_index]  # 中序遍历的左子树
        right_in = inorder[root_index + 1:]  # 中序遍历的左子树
        left_bsf = [x for x in bfsorder if x in left_in]  # 层次遍历的左子树、
        right_bfs = [x for x in bfsorder if x in right_in]
        root.left = self.creatTree(left_bsf, left_in)
        root.right = self.creatTree(right_bfs, right_in)
        return root
 
    def preorder(self, root):
        if not root:
            return []
        return [root.val] + self.preorder(root.left) + self.preorder(root.right)
 
    def postorder(self, root):
        if not root:
            return []
        return self.postorder(root.left) + self.postorder(root.right) + [root.val]
 
s = Solution()
bfsorder = [int(x) for x in input().split()]
inorder = [int(x) for x in input().split()]
root = s.creatTree(bfsorder, inorder)
 
pre = s.preorder(root)
post = s.postorder(root)
print(' '.join(list(map(str,s.leaf))))
print(' '.join(list(map(str,pre))))
print(' '.join(list(map(str,post))))

import java.util.*;

class TreeNode {
	public String val;
	public TreeNode left;
	public TreeNode right;

	public TreeNode(String val) {
		this.val = val;
		this.left = null;
		this.right = null;
	}
}

public class Main {
	public static StringBuilder sb1 = new StringBuilder();
	public static StringBuilder sb2 = new StringBuilder();
	public static StringBuilder sb3 = new StringBuilder();

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String[] levelTranversal = scan.nextLine().split(" ");
		String[] inOrderTranversal = scan.nextLine().split(" ");
		scan.close();
		//
		TreeNode root = getBinaryTree(levelTranversal, inOrderTranversal);
		preOrder(root);
		lastOrder(root);
		//
		System.out.println(sb1.toString().trim());
		System.out.println(sb2.toString().trim());
		System.out.println(sb3.toString().trim());
	}

	public static TreeNode getBinaryTree(String[] levelTranversal, String[] inOrderTranversal) {
		if (inOrderTranversal.length == 0)
			return null;
        //
		int index = 0;
		int inOrderTranversalLength = inOrderTranversal.length;
		TreeNode temp = new TreeNode(levelTranversal[0]);
        // 1. 找到这一轮的根节点
		while (!levelTranversal[0].equals(inOrderTranversal[index])) {
			index++;
		}
		// 2. 两数组存放中序序列划分出来的左边和右边，其分别包含了原二叉树的左子树和右子树
		String[] inOrderTranversalLeft = new String[index];
		String[] inOrderTranversalRight = new String[inOrderTranversalLength - index - 1];
		// 复制填充数据
		System.arraycopy(inOrderTranversal, 0, inOrderTranversalLeft, 0, inOrderTranversalLeft.length);
		for (int i = 0; i < inOrderTranversalRight.length; i++) {
			inOrderTranversalRight[i] = inOrderTranversal[index + i + 1];
		}
		// 3. 存放原二叉树左子树的层级序列，即中序序列划分出来的左边对应的层级序列。右边同理。
        String[] levelTranversalLeft = new String[inOrderTranversalLeft.length]; 
        String[] levelTranversalRight = new String[inOrderTranversalRight.length];
        // 填充数据
        int leftIndex = 0, rightIndex = 0;
        for (int i = 1; i < levelTranversal.length; i++) {
            // 是左的放左，否则就是右的，放右
            if (contains(inOrderTranversalLeft, levelTranversal[i])) {
                levelTranversalLeft[leftIndex++] = levelTranversal[i];
            }else {
                levelTranversalRight[rightIndex++] = levelTranversal[i];
            }
        }
        // 4. 递归处理左节点和右节点
        temp.left = getBinaryTree(levelTranversalLeft, inOrderTranversalLeft);
        temp.right = getBinaryTree(levelTranversalRight, inOrderTranversalRight);
        // 5. 存放叶子节点
        if (temp.left == null && temp.right == null) {
			sb1.append(temp.val).append(" ");
		}
		return temp;
	}
	
	private static boolean contains(String[] arr, String key) {
        for (String element : arr) {
            if (element.equals(key)) return true;
        }
        return false;
    }

	public static void preOrder(TreeNode root) {
		if (root != null) {
			sb2.append(root.val).append(" ");
			preOrder(root.left);
			preOrder(root.right);
		}
	}

	public static void lastOrder(TreeNode root) {
		if (root != null) {
			lastOrder(root.left);
			lastOrder(root.right);
			sb3.append(root.val).append(" ");
		}
	}
}

#include <bits/stdc++.h>
using namespace std;

struct Tree{
    int val;
    Tree *left, *right;
    Tree(int val):val(val), left(NULL), right(NULL){}
};

Tree *Build(vector<int> level, vector<int> in, int s, int e){
    if(level.empty())
        return NULL;
    Tree *T = new Tree(level[0]);
    vector<int> l, r;
    int k=s;
    bool isleft;
    while(in[k]!=level[0])
        k++;
    for(int i=1;i<level.size();i++){
        isleft = false;
        for(int j=s;j<k;j++){
            if(level[i]==in[j]){
                isleft = true;
                break;
            }
        }
        if(isleft)
            l.push_back(level[i]);
        else
            r.push_back(level[i]);
    }
    T->left = Build(l, in, s, k-1);
    T->right = Build(r, in, k+1, e);
    return T;
}

void Leaves(Tree *T, vector<int> &leaf){
    if(!T)
        return;
    if(T->left==NULL && T->right==NULL){
        leaf.push_back(T->val);
        return;
    }
    Leaves(T->left, leaf);
    Leaves(T->right, leaf);
}

void PreOrder(Tree *T, vector<int> &pre){
    if(!T)
        return;
    pre.push_back(T->val);
    PreOrder(T->left, pre);
    PreOrder(T->right, pre);
}

void PostOrder(Tree *T, vector<int> &post){
    if(!T)
        return;
    PostOrder(T->left, post);
    PostOrder(T->right, post);
    post.push_back(T->val);
}

void Print(vector<int> v){
    for(int i=0;i<v.size();i++){
        if(i==v.size()-1)
            cout<<v[i]<<endl;
        else
            cout<<v[i]<<" ";
    }
}

int main(){
    vector<int> a, b;
    int x;
    while(cin>>x){
        a.push_back(x);
        if(getchar()=='\n')
            break;
    }
    while(cin>>x){
        b.push_back(x);
        if(getchar()=='\n')
            break;
    }
    Tree *T = Build(a, b, 0, b.size()-1);
    vector<int> pre, post, leaf;
    Leaves(T, leaf);
    Print(leaf);
    PreOrder(T, pre);
    Print(pre);
    PostOrder(T, post);
    Print(post);
    
    return 0;
}

package com.hhdd.offer.xiaohongshu;

import java.util.Scanner;

/**
 * 根据中序遍历和层次遍历重建一棵二叉树
 * 中序遍历可以确定左子树和右子树的范围
 * 层次遍历可以确定在一个范围的子树中的层级关系
 * 故这二者的序列给定就一定可以唯一的确定一棵二叉树
 */
public class RecoverBTByLeverAndInOrder {

    public static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int value) {
            this.val = value;
        }
    }


    public static TreeNode recoverBT(int[] level, int[] in) {
        return recoverBT(level, in, 0, in.length - 1);
    }

    public static TreeNode recoverBT(int[] level, int[] in, int iStart, int iEnd) {

        int index = findFirstNode(level, in, iStart, iEnd);
        if (index == -1) {
            return null;
        }
        TreeNode tree = new TreeNode(in[index]);
        tree.left = recoverBT(level, in, iStart, index - 1);
        tree.right = recoverBT(level, in, index + 1, iEnd);
        return tree;

    }

    /**
     * 在给定范围的中序遍历中，寻找第一个出现在层次遍历中的节点
     * 这个节点的层级一定是这个中序遍历中层级最高的
     *
     * @param level
     * @param in
     * @return 找到返回中序遍历的下标，没找到返回-1
     */
    public static int findFirstNode(int[] level, int[] in, int iStart, int iEnd) {

        for (int i = 0; i < level.length; i++) {
            for (int j = iStart; j <= iEnd; j++) {
                if (level[i] == in[j]) {
                    return j;
                }
            }
        }
        return -1;
    }

    /**
     * 前序遍历
     *
     * @param head
     */
    public static void preOrder(TreeNode head) {
        if (head == null) {
            return;
        }
        System.out.print(head.val + " ");
        preOrder(head.left);
        preOrder(head.right);
    }

    /**
     * 后序遍历
     *
     * @param head
     */
    public static void postOrder(TreeNode head) {
        if (head == null) {
            return;
        }
        postOrder(head.left);
        postOrder(head.right);
        System.out.print(head.val + " ");
    }

    /**
     * 打印叶子节点
     * 通过魔改前序遍历的方式
     *
     * @param head
     */
    public static void printLeafNode(TreeNode head) {
        if (head == null) {
            return;
        }
        //如果当前节点的左右子树都空，则是叶子节点，打印后直接返回
        if (head.left == null && head.right == null) {
            System.out.print(head.val + " ");
            return;
        }
        printLeafNode(head.left);
        printLeafNode(head.right);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        String[] strings1 = s1.split(" ");
        String[] strings2 = s2.split(" ");
        int[] level = new int[strings1.length];
        int[] in = new int[strings2.length];
        for (int i = 0; i < strings1.length; i++) {
            level[i] = Integer.parseInt(strings1[i]);
            in[i] = Integer.parseInt(strings2[i]);
        }
        TreeNode tree = recoverBT(level, in);

        printLeafNode(tree);
        System.out.println();
        preOrder(tree);
        System.out.println();
        postOrder(tree);
    }


}

var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

//多行输入
var inputArr = [];
rl.on('line', function (input) {
    inputArr.push(input);
    if (inputArr.length === 2) {
        var floor = inputArr[0].split(' ');
        var mid = inputArr[1].split(' ');
        var leaves = [];

        function build(floor, mid) {
            var root = null;
            if (floor.length > 1) {
                var rootMidIdx = mid.indexOf(floor[0]);
                var midLeftList = mid.slice(0, rootMidIdx);
                var midRightList = mid.slice(rootMidIdx + 1);
                var floorLeftList = getSubFromFloor(floor, midLeftList);
                var floorRightList = getSubFromFloor(floor, midRightList);
                root = {
                    val: floor[0],
                    left: build(floorLeftList, midLeftList),
                    right: build(floorRightList, midRightList)
                }
            } else if (floor.length === 1) {
                root = {
                    val: floor[0],
                    left: null,
                    right: null
                };
                leaves.push(floor[0])
            }
            return root
        }

        var head = build(floor, mid);
        console.log(leaves.join(' '));
        var preList = [];
        var lrdList = [];

        function pre(head) {
            if (head.val) {
                preList.push(head.val)
                if (head.left) {
                    pre(head.left)
                }
                if (head.right) {
                    pre(head.right)
                }
            }
        }

        pre(head);

        function lrd(head) {
            if (head.val) {
                if (head.left) {
                    lrd(head.left)
                }
                if (head.right) {
                    lrd(head.right)
                }
                lrdList.push(head.val)
            }
        }

        lrd(head);
        console.log(preList.join(' '));
        console.log(lrdList.join(' '));
    }
});

function getSubFromFloor(floor, list) {
    var ans = [];
    for (var i = 0; i < floor.length; i++) {
        if (list.includes(floor[i])) {
            ans.push(floor[i])
        }
    }
    return ans
}

Python解法

l1 = list(map(int,input().strip().split(" ")))
l2 = list(map(int,input().strip().split(" ")))

class Tree:
    def __init__(self,x):
        self.left = None
        self.right = None
        self.val = x

def fun(l1, l2):
    if len(l1) == 0:
        return None
    root = Tree(l1[0])
    sign = l2.index(l1[0])
    left_l2 = l2[:sign]
    left_l1 = [x for x in l1 if x in left_l2]
    right_l2 = l2[sign+1:]
    right_l1 = [x for x in l1 if x in right_l2]
    root.left = fun(left_l1, left_l2)
    root.right = fun(right_l1, right_l2)
    return root

root = fun(l1,l2)

res1 = []
res2 = []
res3 = []
def dfs(root):
    if root == None:
        return
    if(root.left == None and root.right == None):
        res1.append(root.val)
    res2.append(root.val)
    dfs(root.left)
    dfs(root.right)

def dfs1(root):
    if root == None:
        return
    dfs1(root.left)
    dfs1(root.right)
    res3.append(root.val)

dfs(root)
dfs1(root)

for e in res1:
    print(e, end=" ")
print()
for e in res2:
    print(e, end=" ")
print()
for e in res3:
    print(e,end=" ")
print()

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Tree
{
    int val;
    Tree* left;
    Tree* right;
    Tree(int n):val(n){left=NULL;right=NULL;};
};
Tree* reBuilt(vector<int> layer,const vector<int> &post, int lf,int rig)
{
    if(lf>rig) return NULL;
    if(lf==rig)
    {
        Tree* root=new Tree(layer[0]);
        cout<<root->val<<" ";
        return root;
    };
    Tree* root=new Tree(layer[0]);
    int pos=0;
    for(int i=lf;i<=rig;i++)
        if(post[i]==layer[0])
        {
            pos=i;
            break;
        }
   //找到根所在位置
    vector<int> leftTree;
    vector<int> rightTree;
    for(int i=1;i<layer.size();i++)
    {
        bool isleft=false;
        for(int j=lf;j<pos;j++) //检索左树
            if(post[j]==layer[i])
            {
               isleft=true;
               break;
            }
        if(isleft) leftTree.push_back(layer[i]);
        else rightTree.push_back(layer[i]); 
     }
    //左右树分类完毕
    root->left=reBuilt(leftTree, post, lf, pos-1);
    root->right=reBuilt(rightTree, post, pos+1, rig);
    return root;
}
void PreOrder(Tree *root)
{
    if(root==NULL) 
        return;
    cout<<root->val<<" ";
    PreOrder(root->left);
    PreOrder(root->right);
}
void AfterOrder(Tree *root)
{
     if(root==NULL) 
        return;
    AfterOrder(root->left);
    AfterOrder(root->right);   
    cout<<root->val<<" ";
}
int main()
{
    vector<int> layer;
    vector<int> post;
    string tmp;
    getline(cin,tmp);
    int num=0;
    for(int i=0;i<tmp.length();i++)
    {
       if(tmp[i]!=' ') 
       {
           num*=10;
           num+=tmp[i]-'0';
       }
       if(tmp[i]==' '||i==tmp.length()-1)
        {
            layer.push_back(num);
       //     cout<<layer.back()<<" ";
            num=0;
        }
    }
   // cout<<endl;
    getline(cin,tmp);
    num=0;
    for(int i=0;i<tmp.length();i++)
    {
       if(tmp[i]!=' ') 
       {
           num*=10;
           num+=tmp[i]-'0';
       }
         if(tmp[i]==' '||i==tmp.length()-1)
        {
            post.push_back(num);
         //   cout<<post.back()<<" ";
            num=0;
        }
    }
    //获取数据完成
    Tree* root=reBuilt(layer, post, 0,post.size()-1);
    cout<<endl;
    PreOrder(root);
        cout<<endl;
   AfterOrder(root);
       cout<<endl;
    return 0;
}

//层序遍历和中序遍历重建二叉树
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
    class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        TreeNode(int val){
            this.val = val;
        }
    }
    private ArrayList<Integer> leaves = new ArrayList<Integer>(); 
    private ArrayList<Integer> pre = new ArrayList<>();
    private ArrayList<Integer> last = new ArrayList<>();
    
    //找出数组中某个元素的坐标
    public int findIndex(int[] array, int val){
        for(int i = 0; i < array.length; i++){
            if(array[i] == val)
                return i;
        }
        return -1;
    }
    
    //重建二叉树
    public TreeNode constructT(int[] layer, int[] mid){
        if(layer.length == 0) return null;
        if(layer.length == 1){
            leaves.add(layer[0]);
            TreeNode node = new TreeNode(layer[0]);
            return node;
        }
        //根节点
        int val = layer[0];
        TreeNode root = new TreeNode(val);
        //将中序遍历根据根节点分为左右两棵子树的中序遍历
        int index = findIndex(mid, val);
        if(index == 0)
            root.left = null;
        else{
            int[] left = Arrays.copyOfRange(mid,0, index);
            //在层序遍历数组layer中找出左子树的层序遍历数组
            int[] layerl = new int[left.length];
            for(int i = 0,j=0; i < layer.length&&j < left.length;i++){
                if(findIndex(left,layer[i])!=-1){
                    layerl[j] = layer[i];
                    j++;
                }
            }
            root.left = constructT(layerl,left);
        }
        if(index == mid.length-1)
            root.right = null;
        else{
            int[] right = Arrays.copyOfRange(mid,index+1, mid.length);
            //在层序遍历数组layer中找出右子树的层序遍历数组，为了节省时间，倒序查找
            int[] layerr = new int[right.length];
            for(int i = layer.length-1,j=right.length-1; i >=0&&j >=0;i--){
                if(findIndex(right,layer[i])!=-1){
                    layerr[j] = layer[i];
                    j--;
                }
            }
            root.right = constructT(layerr,right);
        }
        return root;
    }
    
    public void preOrder(TreeNode root){
        if(root != null){
            pre.add(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    
    public void lastOrder(TreeNode root){
        if(root != null){
            lastOrder(root.left);
            lastOrder(root.right);
            last.add(root.val);
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String first = in.nextLine();
        String second = in.nextLine();
        String[] f = first.split(" ");
        String[] s = second.split(" ");
        if(s.length == 0){
            System.out.println();
            System.out.println();
            System.out.println();
            return;
        }
        int[] layer = new int[f.length];
        int[] mid = new int[s.length];
        for(int i = 0; i < f.length; i++){
            layer[i] = Integer.valueOf(f[i]);
            mid[i] = Integer.valueOf(s[i]);
        }
        Main m = new Main();
        TreeNode root = m.constructT(layer,mid);
        m.preOrder(root);
        m.lastOrder(root);
        for(int i = 0; i < m.leaves.size(); i++){
            System.out.print(m.leaves.get(i)+" ");
        }
        System.out.println();
        for(int i = 0; i < m.pre.size(); i++){
            System.out.print(m.pre.get(i)+" ");
        }
        System.out.println();
        for(int i = 0; i < m.last.size(); i++){
            System.out.print(m.last.get(i)+" ");
        }
        System.out.println();
    }
}

import java.util.Arrays;
import java.util.Scanner;

class Treenode{
    public int val;
    public Treenode left;
    public Treenode right;
    public Treenode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
    public Treenode() {
    }    
}
public class Main {
    private static StringBuffer preorderBuffer=new StringBuffer();
    private static StringBuffer postorderBuffer=new StringBuffer();
    private static StringBuffer leafs=new StringBuffer();
    
    
    
    private static void preorder(Treenode root){
        if(root!=null) {
            preorderBuffer.append(root.val+" ");
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    private static void postorder(Treenode root){
        if(root!=null) {
            postorder(root.left);
            postorder(root.right);
            postorderBuffer.append(root.val+" ");
        }
    }
    
    private static Treenode getTreeNode(int[] indexinlevel,int[] midOrder,int from, int to){
        if(to<from) return null;
        if(from==to){
            Treenode result=new Treenode(midOrder[from]);
            leafs.append(midOrder[from]+" ");
            return result;
        }
        int minindex=from;
        for(int i=from+1;i<=to;i++) {
            if(indexinlevel[i]<indexinlevel[minindex])
                minindex=i;
        }
        Treenode result=new Treenode(midOrder[minindex]);
        result.left=getTreeNode(indexinlevel,midOrder,from,minindex-1);
        result.right=getTreeNode(indexinlevel,midOrder,minindex+1,to);
        return result;
    }
    
    private static Treenode getTree(int[] levelOrder,int[] midOrder){
        int[] indexinlevel=new int[midOrder.length];
        for(int i=0;i<midOrder.length;i++) {
            for(int j=0;j<levelOrder.length;j++) {
                if(midOrder[i]==levelOrder[j]) {
                    indexinlevel[i]=j;
                }
            }
        }
        Treenode tree=getTreeNode(indexinlevel,midOrder,0,midOrder.length-1);    
        return tree;
    }
    
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String str1=scanner.nextLine();
        String str2=scanner.nextLine();
        String[] s1=str1.split(" ");
        int[] params1=new int[s1.length];
        String[] s2=str2.split(" ");
        int[] params2=new int[s2.length];
        for(int i=0;i<s1.length;i++)
        {
            params1[i]=Integer.parseInt(s1[i]);
        }
        for(int i=0;i<s2.length;i++)
        {
            params2[i]=Integer.parseInt(s2[i]);
        }
        scanner.close();
        Treenode tree=getTree(params1,params2);
        preorder(tree);
        postorder(tree);
        System.out.println(leafs.toString().trim());
        System.out.println(preorderBuffer.toString().trim());
        System.out.println(postorderBuffer.toString().trim());
    }
}