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

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


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

输入

ABDEC DBEAC

输出

DEBCA
#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)
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)
import java.util.Scanner;
import java.util.Arrays;

// 自定义树节点
class TreeNode {
    TreeNode left;
    TreeNode right;
    char val;
    public TreeNode(char x) {
        val = x;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            String[] s = str.split(" ");
            char[] pre = s[0].toCharArray();    // 前序遍历的序列
            char[] in = s[1].toCharArray();    // 中序遍历的序列
            TreeNode tree = constructTree(pre, in); // 构建二叉树
            printPost(tree); // 打印后序遍历序列
        }
        sc.close();
    }

    // 根据前序遍历序列和中序遍历序列构建二叉树
    private static TreeNode constructTree(char[] pre, char[] in) {
        if (pre.length == 0 || in.length == 0)
            return null;
        char rootVal = pre[0];
        TreeNode root = new TreeNode(rootVal);    // 先构建一个根节点
        for (int i = 0; i < in.length; ++i) {
            if (in[i] == rootVal) {
                root.left = constructTree(Arrays.copyOfRange(pre,1,i+1),
                                         Arrays.copyOfRange(in,0,i));
                root.right = constructTree(Arrays.copyOfRange(pre,i+1,pre.length),
                                          Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
        }
        return root;
    }
    
    // 打印后序遍历序列
    private static void printPost(TreeNode tree) {
        if (tree == null) {
            return;
        } else {
            printPost(tree.left);
            printPost(tree.right);
            System.out.print(tree.val);
        }
    }
}
如果做过《剑指Offer》中的“重建二叉树”那道题的话,那这道题应该可以想到怎么做。
通过前序遍历序列和中序遍历序列可以构建出二叉树,然后再写一个输出后续遍历序列的方法就行了。
发表于 2019-12-11 19:36:08 回复(0)
//因为只需输出后序,所以本人未建立结构体存储数结构。直接递归输出后续
#include <iostream>
#include <cstring>
#include <vector>

using std::string;
using std::cout;
using std::cin;
using std::endl;
using std::vector;

void Calculate(const vector<char>& pre,const vector<char>& mid)
{
if(pre.size()==0 || mid.size()==0)
return;
if(pre.size()==1 || mid.size()==1){
cout<<pre[0];
return;
}
//找到根节点位置
int root = -1;
for(int i=0;i<mid.size();i++){
if(mid[i] == pre[0]){
root = i;
break;
}
}
//获取根节点前面元素的前后序和后面的前后序
    vector<char> preLeft(pre.begin()+1,pre.begin()+root+1);
    vector<char> midLeft(mid.begin(),mid.begin()+root);
    vector<char> preRight(pre.begin()+root+1,pre.end());
    vector<char> midRight(mid.begin()+root+1,mid.end());


//左右根,递归输出
Calculate(preLeft,midLeft);
Calculate(preRight,midRight);
cout<<pre[0];

}

int main()
{
string pre;
string mid;
cin>>pre>>mid;
//把输入存入两个vector中,方便之后操作
vector<char> preVector;
for(int i=0;i<pre.size();i++){
preVector.push_back(pre[i]);
}
vector<char> midVector;
for(int i=0;i<mid.size();i++){
midVector.push_back(mid[i]);
}

Calculate(preVector,midVector);
return 0;
}

编辑于 2019-12-09 21:49:39 回复(0)
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstdio>
 
using namespace std;
struct TreeNode{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x):val(x),left(NULL),right(NULL){}
};
TreeNode* Reconstruct(vector pre,vector vin){
    if(pre.size()==0 || vin.size()==0){
        return NULL;
    }
    TreeNode *root=new TreeNode(pre[0]);
    for(int i=0;i<vin.size();i++)
    {
        if(pre[0]==vin[i])
        {
            vector left_pre,left_vin,right_pre,right_vin;
            /** 左子树的数组*/
            for(int j=0;j<i;j++) {
                left_pre.push_back(pre[j+1]);
                left_vin.push_back(vin[j]);
            }
            /**右子树的数组**/
            for(int j=i+1;j<pre.size();j++)
            {
                right_pre.push_back(pre[j]);
                right_vin.push_back(vin[j]);
            }
            root->left=Reconstruct(left_pre,left_vin);
            root->right=Reconstruct(right_pre,right_vin);
        }
    }
    return root;
}
void postOrder(TreeNode* root){
    if(root!=NULL){
        postOrder(root->left);
        postOrder(root->right);
        printf("%c",root->val);
    }
}
int main(){
    string s1,s2;
    cin>>s1>>s2;
    if(s1.size()!=s2.size()){
        return -1;
    }
    int length=s1.size();
    vector pre,vin;
    for(int i=0;i<length;i++){
        pre.push_back(s1[i]);
        vin.push_back(s2[i]);
    }
    TreeNode* root=Reconstruct(pre,vin);
    postOrder(root);
    return 0;
}

编辑于 2019-10-03 22:18:06 回复(0)
class TreeNode:
    def __init__(self,x):
        self.val=x
        self.left=None
        self.right=None
def reBuildTree(pre,mid):
    if not pre or not mid:
        return ''
    root=TreeNode(pre.pop(0))
    idx=mid.index(root.val)
    root.left=reBuildTree(pre,mid[:idx])
    root.right=reBuildTree(pre,mid[idx+1:])
    return root
def afterTraverse(root):
    if not root:
        return
    afterTraverse(root.left)
    afterTraverse(root.right)
    res.append(root.val)
if __name__=='__main__':
    import sys
    pre,mid=sys.stdin.readline().strip().split()
    pre,mid=list(pre),list(mid)
    root=reBuildTree(pre,mid)
    res=[]
    afterTraverse(root)
    print(''.join(res))

发表于 2019-10-02 11:18:32 回复(0)
首先重建二叉树,然后,后序遍历输出

import java.util.Scanner;
//定义节点
class TreeNode{
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
//主函数
public class Main{
//递归重建二叉树
public static TreeNode beTree(char[] pre,int preStart,int preEnd,char[] in,int inStart,int inEnd){
if(preStart>preEnd||inStart>inEnd){
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
for(int i = inStart;i<=inEnd;i++){
if(in[i]==pre[preStart]){
root.left = beTree(pre,preStart+1,i-inStart+preStart,in,inStart,i-1);
root.right = beTree(pre,i-inStart+preStart+1,preEnd,in,i+1,inEnd);
break;
}
}
return root;
}
//递归,后续遍历二叉树
public static void afterTree(TreeNode t){
if(t!=null){
if(t.left!=null){
afterTree(t.left);
}
if(t.right!=null){
afterTree(t.right);
}

System.out.print(t.val);
}
}
//入口
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
char[] pre = scan.next().toCharArray();
char[] in = scan.next().toCharArray();
TreeNode t = beTree(pre,0,pre.length-1,in,0,in.length-1);
afterTree(t);


}
}
编辑于 2019-09-14 19:53:35 回复(0)
由前序得到根节点,由中序得到左右子树。
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution{
    public:
        //重建二叉树
        struct TreeNode* rebuild(vector<char> pre, vector<char> in){
            int inlen = in.size();
            if (inlen==0)
                return NULL;
            vector<char> left_pre,left_in,right_pre,right_in;
            //根节点head
            TreeNode* head = new TreeNode(pre[0]);
            int gen = 0;
            //记录根节点的下标
            for(int i=0; i<inlen; i++){
                if(in[i]==pre[0]){
                    gen = i;
                    break;
                }
            }
            //根节点左边的序列装入左子树
            for(int i=0; i<gen;i++){
                left_pre.push_back(pre[i+1]);
                left_in.push_back(in[i]);
            }
            //根节点右边的序列装入右子树
            for(int i=gen+1; i<inlen;i++){
                right_pre.push_back(pre[i]);
                right_in.push_back(in[i]);
            }
            //递归,重复上述步骤
            head->left = rebuild(left_pre,left_in);
            head->right = rebuild(right_pre,right_in);
            //重建二叉树完成
            return head;
        }
        //重新后序排列
        void back(TreeNode* head,string* s){
            if(head!=nullptr){
                back(head->left,s);
                back(head->right,s);
                *s += head->val;
            }
        }
};
int main(){
    string pre,in;
    cin>>pre>>in;
    if(pre.size()!=in.size()){
        return -1;
    }
    int leng = in.size();
    Solution s = Solution();
    vector<char> s1,s2;
    for(int i=0 ; i<leng; i++){
        s1.push_back(pre[i]);
        s2.push_back(in[i]);
    }
    TreeNode* root = s.rebuild(s1,s2);
    string result;
    s.back(root,&result);
    cout<<result;
    return 0;
}
    


发表于 2019-09-08 14:01:59 回复(0)
#  递归添加
def getPostOrder(s1, s2):
    if len(s1) == 0 or len(s2) == 0:
        return []
    if len(s1) == 1 or len(s2) == 1:
        return s1
    result = []
    head = s1[0]
    mid = s2.index(head)
    left = getPostOrder(s1[1:mid + 1], s2[0: mid])
    right = getPostOrder(s1[mid + 1:], s2[mid + 1:])
    result.extend(left)
    result.extend(right)
    result.append(head)
    return result


if __name__ == "__main__":
    order = input().split(" ")
    result = getPostOrder(order[0], order[1])
    s = "".join(result)
    print(s)
发表于 2019-09-07 22:20:24 回复(0)
JS拙略的版本...不知道为什么自己IDE上没问题,贴代码上牛客就报return 错误....
let line = readline()
let arr = line.split(" ")
let pre = arr[0].split(" ")
let vin = arr[1].split(" ")

//先重建二叉树
function reConstructBinaryTree(pre, vin) {
    if (pre.length === 0 || vin.length === 0) return null
    let rootIndex = vin.indexOf(pre[0])
    let left = vin.slice(0, rootIndex)
    let right = vin.slice(rootIndex + 1)
    return {
        val: pre[0],
        left: reConstructBinaryTree(pre.slice(1, rootIndex + 1), left),
        right: reConstructBinaryTree(pre.slice(rootIndex + 1), right)
    }
}
//后序遍历
function postOrder(treeNode) {
    let arr = []
    const postNode = (treeNode, callback) => {
        if (treeNode !== null) {
            postNode(treeNode.left, callback)
            postNode(treeNode.right, callback)
            arr.push(callback(treeNode.val))
        }
    }
    postNode(treeNode, callback)
    
    function callback(val) {
        return val
    }
    return arr
}

let treeNode = reConstructBinaryTree(pre, vin)

print(postOrder(treeNode).join(''))



发表于 2019-09-07 16:24:03 回复(0)
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 重建二叉树
def binary(pre, tin):
    if not pre or not tin:
        return None
    root = TreeNode(pre.pop(0))
    index = tin.index(root.val)
    root.left = binary(pre, tin[:index])
    root.right = binary(pre, tin[index+1:])
    return root
# 后序遍历
def postorder(tree):
    if tree != None:
        postorder(tree.left)
        postorder(tree.right)
        btree.append(tree.val)
    return btree
x = input().split()
pre = list(x[0].strip())
tin = list(x[1].strip())
btree = []
print(''.join(postorder(binary(pre, tin))))

发表于 2019-09-02 10:56:01 回复(0)
#include<stdio.h>
#include<string.h>
#define SIZE 1000

void PostArray(char* pre, char* in, char* post, int len );
int main(void) {
    char preOrder[SIZE], inOrder[SIZE];
    char postOrder[SIZE];
    scanf("%s%s",preOrder,inOrder);
    if(strlen(preOrder) != strlen(inOrder) )
        return 0;
    PostArray(preOrder, inOrder, postOrder, strlen(inOrder) );
    printf("%s", postOrder);
    
    return 0;
}
void PostArray(char* pre, char* in, char* post, int len ) {
    if(len == 1) {
        *post = *in;
        return;
    }
    int lenLeft = 0;
    while(lenLeft < len ) {
        if(in[lenLeft] == pre[0] )
            break;
        lenLeft++;
    }
    if(in[lenLeft] != pre[0] )
        exit(0);
    if(lenLeft )
        PostArray(pre+1, in, post, lenLeft );
    if( lenLeft+1 < len )
        PostArray(pre+lenLeft+1, in+lenLeft+1, post+lenLeft, len-lenLeft-1 );
    post[len-1] = pre[0];
    post[len] = '\0';
    return;
}
发表于 2019-09-01 17:41:32 回复(0)
import java.util.Scanner;
import java.util.Arrays;

class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode(char x) { val = x; }
}
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String[] str = str1.split(" ");
        char[] pre = str[0].toCharArray();
        char[] in = str[1].toCharArray();
        TreeNode houxu = chengShu(pre,in);
        postOrder(houxu);
    }
    public static void postOrder(TreeNode tree){
        if(tree == null){
            return;
        }else{
            if(tree.left != null)    postOrder(tree.left);
            if(tree.right != null)    postOrder(tree.right);
            System.out.print(tree.val);
        }
    }
    public static TreeNode chengShu(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 = chengShu(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = chengShu(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }
}

发表于 2019-08-30 23:21:40 回复(0)
#include<iostream>
struct node{
    char value;
    node* leftChild, *rightChild;
};
void postReview(node* root){
    if(root == nullptr)
        return;
    postReview(root->leftChild);
    postReview(root->rightChild);
    std::cout << root->value;
}
const int max = 50;
char preArr[max], inArr[max];
node* createArr(int preL, int preR, int inL, int inR){
    if(preL > preR)
        return nullptr;
    node* root = new node;
    root->value = preArr[preL];
    int index;
    for(index = inL; index <= inR; index++){
        if(inArr[index] == root->value)
            break;
    }
    int numLeft = index - inL;
    root->leftChild = createArr(preL + 1, preL + numLeft, inL, index - 1);
    root->rightChild = createArr(preL + numLeft + 1, preR, index + 1, inR);
    return root;
}
#include <string.h>

int main(){
    scanf("%s", preArr);
    scanf("%s", inArr);
    int size =strlen(preArr) - 1;
    node* root = createArr(0, size, 0, size);
    postReview(root);
    return 0;
}
C++的题解,欢迎指正!

发表于 2019-08-27 21:17:56 回复(0)
大问题不断分解成小问题,使用递归方法:要点是终止条件和问题分解过程中的操作顺序
#include<iostream>
#include<string>
#include<stack>
using namespace std;
unsigned int NUM;
unsigned int pos;
void iteratingPostOrder(string aheahOrder,string midOrder,stack<char> &postOrder)
{
    NUM=aheahOrder.size();
    //返回条件
    if(NUM==0)return;
    char root=aheahOrder[0];
    postOrder.push(root);
    //获取中序 序列中根节点所在位置;
    pos=midOrder.find(root);
    
    string leftTreeMid,rightTreeMid;
    string leftTreeAhead,rightTreeAhead;
    //通过根节点所在位置,拆分
    leftTreeMid.append(midOrder,0,pos);
    leftTreeAhead.append(aheahOrder,1,pos);
    rightTreeMid.append(midOrder,pos+1,NUM-1-pos);
    rightTreeAhead.append(aheahOrder,pos+1,NUM-1-pos);
    //递归,送入“前序-中序”对,注意顺序,由于使用压栈操作,所以顺序应该与后序完全相反:根->右->左
    iteratingPostOrder(rightTreeAhead,rightTreeMid,postOrder);
    iteratingPostOrder(leftTreeAhead,leftTreeMid,postOrder);
}

int main()
{
    string str1,str2;
    std::cin>>str1>>str2;
    stack<char> postOrder;
    iteratingPostOrder(str1,str2,postOrder);
    //cout<<postOrder.size()<<endl;
    while(postOrder.size()!=0)
    {
        cout<<postOrder.top();
        postOrder.pop();
    }
    cout<<endl;
    return 0;
}

发表于 2019-08-26 22:44:30 回复(0)