首页 > 试题广场 >

二叉树后序遍历

[编程题]二叉树后序遍历
  • 热度指数:4915 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个二叉树的前序遍历和中序遍历的序列,输出对应这个二叉树的后续遍历序列。

输入描述:
输入为一行。 两个字符串,分别表示二叉树的前序遍历和中序遍历结果,用空格分隔。保证数据合法


输出描述:
对应输出后序遍历序列
示例1

输入

ABDEC DBEAC

输出

DEBCA
Java解题--不用重构树来推导后序遍历
import java.util.Scanner;
public class Main{
    
    static StringBuilder result = new StringBuilder();
    public static String postByPreAndIn(String pre,String in){
        if(pre.length() == 0 || in.length() == 0) return null;
        int mid = -1;
        for(int i = 0; i < in.length();i++){
            if(in.charAt(i) == pre.charAt(0)){
                mid = i;
                break;
            }
        }
        postByPreAndIn(pre.substring(1,mid+1),in.substring(0,mid));
        postByPreAndIn(pre.substring(mid+1,pre.length()),in.substring(mid+1,in.length()));
        result.append(pre.charAt(0));
        return result.toString();
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String pre = sc.next();
        String in = sc.next();
        System.out.println(postByPreAndIn(pre,in));
    }
    
    
    
}


编辑于 2020-03-07 14:40:50 回复(0)
#include<iostream>
#include<vector>
using namespace std;

//构建二叉树结点
struct BTreeNode
{
	char data;
	BTreeNode* left;
	BTreeNode* right;
    BTreeNode(char x):data(x),left(NULL),right(NULL){}
};

//根据父节点将二叉树分为左右子树
vector<char> m_copy(vector<char> &v, int l, int r)
{
    return vector<char> (v.begin()+l, v.begin()+r);
}

//根据前序序列和中序序列重建二叉树
BTreeNode* reConstructBTree(vector<char> pre, vector<char> vin)
{
    if(pre.size() == 0 || vin.size() == 0)
        return NULL;

    BTreeNode* node = new BTreeNode(pre[0]);

    for(unsigned long i = 0; i < vin.size(); ++i)
    {
        if(pre[0] == vin[i])
        {
            node->left = reConstructBTree(m_copy(pre,1,i+1),m_copy(vin,0,i));
            node->right = reConstructBTree(m_copy(pre,i+1,pre.size()),m_copy(vin,i+1,vin.size()));
        }
    }
    return node;
}

//后序遍历二叉树
void PastOrder(BTreeNode* p)
{
    if(p == NULL)
        return;

    PastOrder(p->left);
    PastOrder(p->right);
    cout<<p->data;
}

int main()
{
    string s1,s2;
    cin>>s1>>s2;
    if(s1.size()!=s2.size())
    {
        return -1;
    }
    int length=s1.size();
    vector<char> pre,vin;
    for(int i=0;i<length;i++)
    {
        pre.push_back(s1[i]);
        vin.push_back(s2[i]);
    }
    BTreeNode* res = reConstructBTree(pre, vin);
    PastOrder(res);
    return 0;
}
参考:https://blog.csdn.net/qq_26079093/article/details/102061002
编辑于 2019-10-04 11:48:19 回复(0)

看到很多人都是重建二叉树再后序遍历,其实可以直接算出后序遍历的字符串。

前序:ABDEC
中序:DBEAC
后序:DEBCA

第一轮递归中,我们可以找到规律:
根节点为A,左树节点为DBE,右树节点为C。
从这可以看出后序的结果是左树节点 + 右树节点 + A拼起来的,从而在每次递归里,将A放在最后即可。

完整代码:

var [preOrder, midOrder] = readline().split(/\s+/);
function computedPost(pre, mid) {
    var root = pre[0], strLen = pre.length;
    if (strLen < 1) {
        return ''
    } else if (strLen < 2) {
        return root;
    }

    var m = 0
    while (mid[m] !== root) {
        m++
    }

    return computedPost(
        pre.slice(1, m + 1),
        mid.slice(0, m)
    ) + computedPost(
        pre.slice(m + 1),
        mid.slice(m + 1)
    ) + root
}
print(computedPost(preOrder, midOrder))

编辑于 2020-01-29 10:42:24 回复(1)
import java.util.*;
    class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode(char val){
            this.val = val;
        }
    }
public class Main{
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            char[] pre = sc.next().toCharArray();
            char[] in = sc.next().toCharArray();
            TreeNode node = build(pre,in);
            after(node);
        }
        public static TreeNode build(char[] pre,char[] in){
            if(pre.length==0||in.length==0)
                return null;
            TreeNode node = new TreeNode(pre[0]);
            for(int i =0;i<in.length;i++){
                if(in[i]==pre[0]){
                    node.left=build(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                    node.right=build(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                }
            }
            return node;
        }
        public static void after(TreeNode node){
            if(node == null)
                return;
            after(node.left);
            after(node.right);
            System.out.print(node.val);
        }
    }

发表于 2020-02-29 16:06:31 回复(0)
观察前中后三种遍历序列结构:
前序:NLR
中序:LNR
后序:LRN
可以发现,每次先从前序序列找到,然后从中序序列分出子树,最后,按照的顺序拼接成后序序列,即可。
对于二叉树问题,一定要明确,二叉树是一种递归定义的结构!
按照手动模拟的思路,可以写出代码:
#include<iostream>
#include<vector>
using namespace std;
typedef vector<char> VC;

int find(VC v, int start, int end, char t){
    int i;
    for(i=start;i<=end;i++)
        if(v[i]==t) break;
    return i;
}

VC reConstruct(VC pre,int l1,int r1,VC vin,int l2, int r2){
    VC res;
    if(l1<=r1){
        res.push_back(pre[l1]);
        int div=find(vin,l2,r2,pre[l1]);
        VC lv,rv;
        lv=reConstruct(pre, l1+1, l1+div-l2, vin, l2, div-1);
        rv=reConstruct(pre, l1+div-l2+1, r1, vin, div+1, r2);
        res.insert(res.begin(), rv.begin(), rv.end());
        res.insert(res.begin(), lv.begin(), lv.end());
    }
    return res;
}

VC reConstructBinaryTree(VC pre,VC vin) {
    return reConstruct(pre,0,pre.size()-1,vin,0,vin.size()-1);
}

int main(){
    //NLR LNR LRN
    string a,b;
    cin>>a>>b;
    VC pre(a.length()),in(b.length());
    for(int i=0;i<a.length();i++){
        pre[i]=a[i];
        in[i]=b[i];
    }
    VC r=reConstructBinaryTree(pre,in);
    for(int i=0;i<r.size();i++)
        cout<<r[i];
    cout<<endl;
    return 0;
}
若把vector<char>换成string,会更快一些;
若直接输出而不用容器暂存,也能更快。
发表于 2020-02-15 13:42:06 回复(0)
import sys
# 定义节点
class TreeNode(object):
    def __init__(self,val,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right
# 重建二叉树
def rebuild(pre,pos):
    if pre =='':
        return 
    val = pre[0]
    index = pos.index(val)
    root = TreeNode(val)
    root.left = rebuild(pre[1:1+index],pos[:index])
    root.right = rebuild(pre[1+index:],pos[index+1:])
    return root
# 后续遍历第归实现
def posorder(root):
    if root is None:
        return
    posorder(root.left)
    posorder(root.right)
    print(root.val,end='')
if __name__ =="__main__":
    line = sys.stdin.readline().strip()
    pre,pos = line.split()
    root = rebuild(pre,pos)
    res = posorder(root)

发表于 2019-09-07 21:33:09 回复(0)
#include <iostream>
#include <vector>

using namespace std;
struct TreeNode{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x):val(x),left(NULL),right(NULL){}
};

TreeNode* Reconstruct(vector<char> pre,vector<char> vin){
    int length=pre.size();
    if(length==0){
        return nullptr;
    }
    TreeNode *root=new TreeNode(pre[0]);
    if(length==1){
        if(pre==vin){
            return root;
        }
        else
            return nullptr;
    }
    int rootInorder=0;
    while(rootInorder<length&&vin[rootInorder]!=pre[0]){
        rootInorder++;
    }
    if(rootInorder==length-1&&vin[rootInorder]!=pre[0]){
        return nullptr;
    }
    vector<char> left_pre,left_vin,right_pre,right_vin;
    for(int i=0;i<rootInorder;i++){
        left_pre.push_back(pre[i+1]);
        left_vin.push_back(vin[i]);
    }
    for(int i=rootInorder+1;i<length;i++){
        right_pre.push_back(pre[i]);
        right_vin.push_back(vin[i]);
    }
    root->left=Reconstruct(left_pre,left_vin);
    root->right=Reconstruct(right_pre,right_vin);
    return root;
}

void Back(TreeNode* root,string* s){
    if(root!=nullptr){
        Back(root->left,s);
        Back(root->right,s);
        *s+=root->val;
    }
}

int main(){
    string s1,s2;
    cin>>s1>>s2;
    if(s1.size()!=s2.size()){
        return -1;
    }
    int length=s1.size();
    vector<char> pre,vin;
    for(int i=0;i<length;i++){
        pre.push_back(s1[i]);
        vin.push_back(s2[i]);
    }
    TreeNode* root=Reconstruct(pre,vin);
    string s;
    Back(root,&s);
    cout<<s;
    return 0;
}

发表于 2019-08-27 19:07:23 回复(0)
先重建二叉树,然后使用后序遍历就可以了
class Treenode:
    def __init__(self,val):
        self.val = val
        self.leftchild = None
        self.rightchild = None

def rebuildtree(prorder,inorder):

    if len(prorder) == 0:
        return None
    else:
        root = Treenode(prorder[0])
        k = inorder.index(prorder[0])

        root.leftchild = rebuildtree(prorder[1:k+1],inorder[:k])
        root.rightchild = rebuildtree(prorder[k+1:],inorder[k+1:])

    return root

def postorder(root):
    if root is not None:
        postorder(root.leftchild)
        postorder(root.rightchild)
        a.append(root.val)

import sys
zz = list(sys.stdin.readline().strip().split())
z1 = list(zz[0])
z2 = list(zz[1])
a = []
root = rebuildtree(z1,z2)
postorder(root)
print(''.join(a))


发表于 2019-08-20 16:55:01 回复(0)
#include<stdio.h>
int pre[1000],in[1000],lch[10000],rch[10000],n=0;
int build(int,int,int,int);
void post(int);
int main(){
    char s1[1000],s2[1000];
    //freopen("input.txt","r",stdin);
    scanf("%s%s",s1,s2);
    for(int i=0;s1[i]!='\0';i++){
        int tmp1=s1[i]-'A'+1,tmp2=s2[i]-'A'+1;
        pre[n]=tmp1,in[n++]=tmp2;    
    }
    int root=build(0,n-1,0,n-1);
    post(root);
}
int build(int l1,int r1,int l2,int r2){
    if(l1>r1) return 0;
    int root=pre[l1],cnt=0,i;
    for(i=l2;i<=r2&&in[i]!=root;i++,cnt++);
    lch[root]=build(l1+1,l1+cnt,l2,i-1);
    rch[root]=build(l1+cnt+1,r1,i+1,r2);
    return root;
}
void post(int root){
    if(!root) return;
    post(lch[root]),post(rch[root]);
    printf("%c",'A'+root-1);    
}

发表于 2017-11-01 11:00:46 回复(0)
#include<iostream>
#include<cstring>
using namespace std;
void findpost(const char*pre,const char*in,char* post,int n){
    if(n==0)return;
    int i;
    for(i=0;;++i){
        if(in[i]==pre[0])break;
    }
    findpost(pre+1,in,post,i);
    findpost(pre+i+1,in+i+1,post+i,n-i-1);
    post[n-1]=pre[0];
}
int main(){
    char pre[1000]="",in[1000]="",post[1000]="";
    cin>>pre>>in;
    findpost(pre,in,post,strlen(pre));
    cout<<post<<endl;
    return 0;
}

发表于 2017-09-13 20:16:29 回复(0)
先建树,后遍历输出:
import java.util.*;
class TreeNode{
    char val;
    TreeNode left = null;
    TreeNode right = null;
    TreeNode(char val) { this.val = val;}
}
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            String[] str = sc.nextLine().split(" ");
            char []pre = str[0].toCharArray();
            char []in = str[1].toCharArray();
            TreeNode root = reCon(pre, in);
            find(root);
        }
    }
    public static TreeNode reCon(char[] pre, char[] in){
        if (pre.length==0||in.length==0)
            return null;
        TreeNode root = new TreeNode(pre[0]);
        for (int i=0;i<in.length;i++)
            if (in[i]==pre[0]){
                root.left = reCon(
                Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = reCon(
                Arrays.copyOfRange(pre,i+1,in.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        return root;
    }
   //递归后序遍历方法:
    public static void find(TreeNode root){
        if (root == null) return;
        find(root.left);
        find(root.right);
        System.out.print(root.val);
    }
/*    非递归后序遍历方法:
    public static void find(TreeNode root){
        if (root == null) return;
        TreeNode pCur = root;
        TreeNode pLastVisit = null;
        Stack<TreeNode> stack = new Stack<>();
        while (pCur != null){
            stack.push(pCur);
            pCur = pCur.left;
        }
        while (!stack.isEmpty()){
            pCur = stack.pop();
            if (pCur.right == null||pLastVisit == pCur.right){
                System.out.print(pCur.val);
                pLastVisit = pCur;
            }
            else {
                stack.push(pCur);
                pCur = pCur.right;
                while(pCur != null){
                    stack.push(pCur);
                    pCur = pCur.left;
                }
            }
        }
     }
*/
}


编辑于 2019-09-22 20:31:55 回复(0)
//直接左子树加右子树加根节点输出
#include<bits/stdc++.h>
using namespace std;

string pos(string pre,string vin){
    string res="";
    if(pre.size()==0)return res;
    char temp=pre[0];
    int tag=0;
    for(int i=0;i<vin.size();i++){
        if(vin[i]==temp){
            tag=i;
            break;
        }
    }
    string preleft(pre.begin()+1,pre.begin()+1+tag);
    string preright(pre.begin()+1+tag,pre.end());
    string vinleft(vin.begin(),vin.begin()+tag);
    string vinright(vin.begin()+1+tag,vin.end());
    res=pos(preleft,vinleft)+pos(preright,vinright)+temp;
    if(res.size()==pre.size())return res;
}
int main(){
    string pre, vin;
	cin >> pre >> vin;
    cout<<pos(pre,vin);
    return 0;
}


发表于 2020-02-24 12:45:19 回复(1)
#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<iostream>

using namespace std;

string pre = "", in = "";
//树的ADT
typedef struct Tree{
	char data;
	Tree* lchild;
	Tree* rchild;
} T, *Tnode;
//后续遍历
void hOrder(T *t) {
	//注意非空才打印
	if(t != NULL) {
		hOrder(t->lchild);
		hOrder(t->rchild);
		cout<<t->data;
	}
}
int findRoot(char a, string s) {
	for(int i = 0; i < s.size(); ++i)
		if(s[i] == a)
			return i;
	return -1;
}
//依据前序和中序序列建立树
Tnode build(int from, int to) {
	//不要忘了返回Null不然会bug
	if(from > to)
		return NULL;

	Tnode root = (Tnode)malloc(sizeof(T));
	int rootIndex = 0xffff, t = 0;
	//寻找划分后的子树的根, 即划分序列中在前序序列中下标最小的那个
	for(int i = from; i <= to; i++) {
		//用划分好的中序序列在前序序列中寻找下标
		t = findRoot(in[i], pre);
		rootIndex = rootIndex < t ? rootIndex : t;
	}

	//递归建立树
	root->data = pre[rootIndex];

	//根坐标更新为中序的坐标进行划分
	rootIndex = findRoot(root->data, in);
	root->lchild = build(from, rootIndex-1);
	root->rchild = build(rootIndex+1, to);

	return root;
}
T* buildTree() {
	
	Tnode root = (Tnode)malloc(sizeof(T));
	root->data = pre[0];
	//划分序列得是中序序列根的下标
	int rootIndex = findRoot(pre[0], in);
	root->lchild = build(0, rootIndex-1);
	root->rchild = build(rootIndex+1, pre.size()-1);
	
	return root;
}
int main(int argc, char* argv[])
{
	cin>>pre>>in;
	T* t = buildTree();
	hOrder(t);
	cout<<endl;
	return 0;
}


发表于 2023-02-08 19:45:35 回复(0)
// 中规中矩的解题思路
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        
        char[] pre = s1.toCharArray();
        char[] vin = s2.toCharArray();
        
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < vin.length; i++) {
            map.put(vin[i], i);
        }
        
        TreeNode root = process(pre, 0, pre.length, vin, 0, vin.length, map);
        prePrint(root);
    }
    
    public static TreeNode process(char[] pre, int preBegin, int preEnd, char[] vin, int vinBegin, int vinEnd, Map<Character, Integer> map) {
        if (preBegin >= preEnd || vinBegin >= vinEnd) {
            return null;
        }
        
        int index = map.get(pre[preBegin]);
        TreeNode root = new TreeNode(vin[index]);
        int count = index - vinBegin;
        root.left = process(pre, preBegin + 1, preBegin + count + 1, vin, vinBegin, index, map);
        root.right = process(pre, preBegin + count + 1, preEnd, vin, index + 1, vinEnd, map);
        return root;
    }
    
    public static void prePrint(TreeNode root) {
        if (root == null) {
            return;
        }
        prePrint(root.left);
        prePrint(root.right);
        System.out.print(root.val);
    }
}

class TreeNode {
    Character val;
    TreeNode left;
    TreeNode right;
    public TreeNode(Character val) {
        this.val = val;
    }
}

发表于 2022-09-04 14:51:35 回复(0)
import java.util.*;

public class Main {
    // 二叉树的后序遍历-同样是递归干嘛造树
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] s = in.nextLine().split(" ");
        String pre = s[0], mid = s[1];
        for (int i = 0; i < mid.length(); i++) { // 存在map中提高效率
            map.put(mid.charAt(i), i);
        }
        fun(pre, mid, 0, pre.length()-1, 0, mid.length()-1);
        System.out.println(res);
    }
    static Map<Character, Integer> map = new HashMap<>();
    static StringBuilder res = new StringBuilder();
    // 递归处理-注意后序是左右根递归的时候是根右左
    public static void fun(String pre, String mid, int pstart, int pend, int mstart, int mend) {
        if (pstart <= pend) {
            int idx = map.get(pre.charAt(pstart));
            res.insert(0, pre.charAt(pstart));
            fun(pre, mid, pstart + (idx - mstart) + 1, pend, idx + 1, mend);
            fun(pre, mid, pstart + 1, pstart + (idx - mstart), mstart, idx - 1);
        }
    }
}
发表于 2022-07-24 13:44:03 回复(0)
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct NodeTree{
    char data;
    struct NodeTree *pl;
    struct NodeTree *pr;
};//构造二叉树
vector<char> pre;
vector<char> in;
NodeTree* reconstruction(vector<char> &pre,vector<char> &in,int p_first,int p_end,int i_first,int i_end)
{
    if(p_first>p_end)
        return nullptr;
    NodeTree* T=new NodeTree;
    T->data=pre[p_first];
    for(int i=i_first;i<=i_end;i++)
    {
        if(in[i]==pre[p_first])
        {
            T->pl=reconstruction(pre,in,p_first+1,p_first+i-i_first,i_first,i-1);
            T->pr=reconstruction(pre,in,p_first+i-i_first+1,p_end,i+1,i_end);
            break;
        }
    };
    return T;
}//重构二叉树
void backtravel(NodeTree* T)
{
    if(T)
    {   
        backtravel(T->pl);
        backtravel(T->pr);
        cout<<T->data;

    }
};
//后序遍历

    int main()
{
 string a,b;
    
  cin>>a>>b;
        if(a.size()!=b.size())
        { 
            return -1;
        }
    for(int i=0;i<=a.size()-1;i++)
    {
        pre.push_back(a[i]);
        in.push_back(b[i]);
    };
   NodeTree* root;
   root=reconstruction(pre,in,0,pre.size()-1,0,in.size()-1);
   backtravel(root);
};

发表于 2020-06-08 21:04:26 回复(0)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s=br.readLine();//别忘了抛出异常
        String[] ss=s.split(" ");
        char[] pre=ss[0].toCharArray();
        char[] in=ss[1].toCharArray();
        postOrder(pre,0,pre.length-1,in,0,in.length-1);
    }
    public static TreeNode postOrder(char[] pre,int startPre,int endPre,char[] in,int startIn,int endIn){
        if(startPre>endPre || startIn>endIn){
            return null;
        }
        TreeNode root=new TreeNode(pre[startPre]);
        for(int i=startIn;i<=endIn;i++){
            if(in[i]==pre[startPre]){
                root.left=postOrder(pre,startPre+1,i-startIn+startPre,in,startIn,i-1);//left
                root.right=postOrder(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);//right
            }
        }
        System.out.print(root.data);//输出,要放在后面,从里向外输出
        return root;
        
        
    }
}
class TreeNode{
    TreeNode left;
    TreeNode right;
    char data;
    public TreeNode(char data){
        this.data=data;
    }
}
发表于 2020-06-02 21:22:31 回复(0)
无需建树的Java实现
import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-04-24 17:06
 * @Description: 二叉树后序遍历
 * @version: 1.0
 */
public class Main {
    private static void getTree(String pre, int preL, int preR, String mid, int midL, int midR) {
        if (preL>preR)
            return ;
        if (preL==preR){
            System.out.print(pre.charAt(preL));
            return;
        }
        for (int i=midL;i<=midR;i++){
            if (pre.charAt(preL)==mid.charAt(i)){
               getTree(pre,preL+1,i-midL+preL,mid,midL,i-1);
               getTree(pre,i-midL+preL+1,preR,mid,i+1,midR);
            }
        }
        System.out.print(pre.charAt(preL));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String pre = sc.next();
        String mid = sc.next();
        getTree(pre,0,pre.length()-1,mid,0,mid.length()-1);
        sc.close();
    }
}
建树Java实现:
import java.util.Scanner;
 
/**
 * @Author: coderjjp
 * @Date: 2020-04-24 17:06
 * @Description: 二叉树后序遍历
 * @version: 1.0
 */
public class Main {
    private class TreeNode{
        TreeNode left;
        TreeNode right;
        char val;
        public TreeNode(char val) {
            this.val = val;
        }
    }
 
    public StringBuilder getLast(char[] pre,char[] mid){
        TreeNode root = getTree(pre,0,pre.length-1,mid,0,mid.length-1);
        StringBuilder sb = new StringBuilder();
        lastSort(root,sb);
        return sb;
    }
 
    private TreeNode getTree(char[] pre, int preL, int preR, char[] mid, int midL, int midR) {
        if (preL>preR)
            return null;
        if (preL==preR)
            return new TreeNode(pre[preL]);
        TreeNode root = new TreeNode(pre[preL]);
        for (int i=midL;i<=midR;i++){
            if (pre[preL]==mid[i]){
                root.left=getTree(pre,preL+1,i-midL+preL,mid,midL,i-1);
                root.right=getTree(pre,i-midL+preL+1,preR,mid,i+1,midR);
            }
        }
        return root;
    }
 
    private void lastSort(TreeNode root, StringBuilder sb) {
        if (root==null)
            return;
        lastSort(root.left,sb);
        lastSort(root.right,sb);
        sb.append(root.val);
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] pre = sc.next().toCharArray();
        char[] mid = sc.next().toCharArray();
        StringBuilder last = new Main().getLast(pre,mid);
        System.out.println(last);
        sc.close();
    }
}



发表于 2020-04-24 18:08:10 回复(0)
根据先序序列和中序序列 模仿遍历二叉树的 中-右-左 访问顺序依次将节点入栈result,结果输出依次出栈输出即可。
import java.util.Scanner;
import java.util.Stack;

public class Main {

    private static Stack<Character> result = new Stack<>();

    /**
     *
     * @return
     */
    public static String print(){
        if(result == null || result.size()==0) return "";
        String str = "";
        while (!result.empty())
        {
            str += result.pop();
        }
        return str;
    }

    /**
     *
     * @param pre
     * @param mid
     * @return 返回後序遍歷
     */
    public static String after(String pre, String mid){
        if(pre == null || pre == "" || mid == null || mid == "" || pre.length() != mid.length() || pre.length() == 0 || mid.length() ==0) return "";
        char father = pre.charAt(0);
        Character character = new Character(father);
        result.push(character);
        int dex = 0;
        while (dex<pre.length() && father != mid.charAt(dex++));
        dex--;
        
          if(dex + 1 < pre.length())
          after(pre.substring(dex + 1, pre.length()), mid.substring(dex + 1, mid.length()));
          if(dex != 0)
          after(pre.substring(1, dex+1), mid.substring(0, dex));
     
        return "";
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String pre = in.next();
        String mid = in.next();
        //System.out.println(pre + " " + mid);
        after(pre,mid);
        System.out.println(print());
    }
}
编辑于 2020-04-18 17:53:38 回复(0)

题目思路挺清晰的,我是先通过前序和中序构造出树结构,再通过递归遍历后序。
在构造二叉树的时候,用哈希表寻找中序遍历中的根节点个很方便。代码如下:

#include <bits/stdc++.h>

using namespace std;
struct TreeNode{
    char val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char ch) : val(ch), left(NULL), right(NULL) {}
};

unordered_map<char, int> h;
TreeNode* dfs(vector<char> &preorder, vector<char> &inorder, int pl, int pr, int il, int ir)
{
    if(pl > pr) return NULL;
    int gen = preorder[pl];
    int pos = h[gen];
    int len = pos - il;
    auto root = new TreeNode(gen);
    root->left = dfs(preorder, inorder, pl + 1, pl + len, il, pos - 1);
    root->right = dfs(preorder, inorder, pl + len + 1, pr, pos + 1, ir);
    return root;
}
TreeNode* Construct(vector<char>& preorder, vector<char>& inorder) {
    int n = inorder.size();
    if(n <= 0) return NULL;
    for(int i = 0; i < n; i++) h[inorder[i]] = i;
    return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
}

void postSearch(TreeNode* root, vector<char> &postorder)
{
   // if(!root) return ;
    if(root->left) postSearch(root->left, postorder);
    if(root->right) postSearch(root->right, postorder);
    postorder.push_back(root->val);
}
int main()
{
    string a, b;
    cin >> a >>b;
    int n = a.size();

    vector<char> preorder, inorder, postorder;
    for(int i = 0; i < n; i++)
    {
        preorder.push_back(a[i]);
        inorder.push_back(b[i]);
    }
    TreeNode *root = Construct(preorder, inorder);
    postSearch(root, postorder);

    for(int i = 0; i < n; i++) cout << postorder[i];
    return 0;
}
发表于 2020-04-02 09:08:31 回复(0)