二叉树后序遍历

#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;
}

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

前序：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))

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);
        }
    }

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)

#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;
}

#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);    
}

#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;
}

#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;
}

// 中规中矩的解题思路
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;
    }
}

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);
        }
    }
}

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());
    }
}

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

#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;
}