在做数据结构面试题的时候我们会经常发现有关二叉树的题目总是这样的 
 栗子： 
 已知某二叉树先序为……中序为……求后序 
 已知某二叉树中序为……后序为……求先序 
 需要注意的是（我们只能够通过已知先序中序求后序或已知中序后序求先序，而不能够已知先序和后序求中序） 
 下面总结一下两种题的做法
 
 
首先回顾知识点
 
二叉树先序遍历 根结点—->左子树—->右子树
二叉树中序遍历 左子树—->根结点—->右子树
二叉树后序遍历 左子树—->右子树—->根结点 
 这个非常好记忆，就是看根结点的位置就可以了
 
 
第一种 
 已知一个二叉树的先序遍历结果为：ABCDEFGH，中序遍历结果为BDCEAFHG，求该二叉树的后序遍历。
 
思路：拿到这样的题，我们要先根据两种遍历顺序把原始二叉树画出来，然后再根据后序遍历的规则解出后序遍历。
 
解析：首先看先序遍历的第一个结点为A，那么根据先序遍历规则先访问根结点，那么A肯定是根结点了。然后根据中序遍历规则先访问左子树中间访问根结点。那么我们可以得出BCDE是根结点A的左子树FHG是根结点A的右子树。那么左子树BCDE当中又怎么排序呢？这个时候我们再来看先序遍历，A结点之后先序先遍历B，说明B一定是根结点A左子树的根结点。如下图 
  
 然后我们再看中序遍历，B是第一个，说明B结点没有左子树，CDE是B的右子树，然后我们想知道CDE如何排序，再次看先序遍历，这个时候先序遍历AB已经排出来。过来是C，说明C是B结点右子树的根结点。可以画出下图 
  
 接下来我们再次看中序遍历，中序遍历B接下来是D，而且我们已经知道C是B右字数的根结点，那么我们根据中序先访问左子树然后访问根结点，就知道D是C结点的左子树。那么E理所当然应该是C结点的右子树。可以画出如下图 
  
 这样我们的左子树就画好了，接下来处理FGH。我们看到F在先序和中序中都先出现，我们就可以确定F是右子树的根结点，并且F没有左子树。接下来先序出现的是G，而中序中G是最后出现的。所以G是F右子树的根结点而H是G的左子树。这样我们就确定了原始树的样子如下图 
 
 
最后一步： 
 得知原始树 
 我们按照后序遍历的规则，先访问左子树再访问右子树最后访问根结点 
 可以得到后续遍历的顺序为DECBHGFA
 
 
哈哈，学会了先序中序求后序，我们再看第二种，已知中序后序求先序
 
直接上题目 
 第二种 
 已知一个二叉树的中序遍历结果为： BDACE，后序遍历结果为 DBECA，求该二叉树的先序遍历。
 
按照第一题的做法，首先我们知道后序遍历最后遍历根结点，所以A结点一定是这棵树的根结点，然后我们再开中序遍历的结果，A结点是根结点，所以BD是A结点的左子树，CE是根结点的右子树。先看BD。根据中序先遍历左子树然后遍历根结点最后遍历右子树顺序为BD，而后序先遍历左子树再遍历右子树最后遍历根结点顺序为DB。所以可以推出B是A的左子树的根结点，且B没有左子树，B的右子树是D。可画出下图 
 
 
接下来我们来看A的右子树。剩下EC两个结点，我们再次看中序与后序遍历的结果。根据中序先遍历左子树然后遍历根结点最后遍历右子树顺序为CE，而后序先遍历左子树再遍历右子树最后遍历根结点顺序为EC。则我们可以推出C应该是A结点右子树的根结点，而E应该是C结点的右子树。这样我们就可以画出原始树如下图 
 
 
根据原始树，我们可以按照先序遍历的顺序得到先序遍历结果：ABDCE
 
总结：掌握先中后遍历的规则，然后结合先中或者中后以及遍历规则画出原始树，然后根据原始树求出先序或者后序！！

已知先序中序求后序
 
public class BinaryTree1 {
    private Node root;

    public void postOrder(){
        postOrder(root);
    }

    //二叉树构造完毕之后进行后续遍历
    private void postOrder(Node localroot) {
        if(localroot!=null){
            postOrder(localroot.left);
            postOrder(localroot.right);
            System.out.print(localroot.data+" ");
        }
    }

    public void InitTree(int[] preOrder,int[] inOrder){
        this.root=InitTree(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
    }

    /**
     *
     * @param preOrder 先序遍历的数组
     * @param start1 递归每次遍历的数据段在先序遍历数组中的起始位置
     * @param end1 递归每次遍历的数据段在先序遍历数组中的终止位置
     * @param inOrder 中序遍历的数组
     * @param start2 递归每次遍历的数据段在中序遍历数组中的起始位置
     * @param end2 递归每次遍历的数据段在中序遍历数组中的终止位置
     * @return 返回本次递归所构造完毕的树的根节点（从子结点向上依次返回）
     */
    private Node InitTree(int[] preOrder, int start1, int end1, int[] inOrder, int start2, int end2) {
        if(start1>end1||start2>end2){
            return null;
        }
        int rootData=preOrder[start1];
        Node head=new Node(rootData);
        int rootindex=findIndexInArray(inOrder,rootData,start2,end2);
        /**
         * offset为以本次递归构造的节点为根节点的左子树的节点个数
         */
        int offset=rootindex-start2-1;
        Node left=InitTree(preOrder,start1+1,start1+offset+1,inOrder,start2,start2+offset);
        Node right=InitTree(preOrder,start1+offset+2,end1,inOrder,rootindex+1,end2);
        head.left=left;
        head.right=right;
        return head;
    }

    //检索出递归方法每次构造的节点在中序遍历数组中的索引
    public int  findIndexInArray(int[] a,int x,int begin,int end){
        for (int i = begin; i <=end; i++) {
            if(a[i]==x){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        BinaryTree1 biTree=new BinaryTree1();
        int[] preOrder={2,1,8,7,4,3,6,5,7,9};
        int[] inorder={1,2,3,4,5,6,7,7,8,9};
        biTree.InitTree(preOrder,inorder);
        System.out.println("后序遍历");
        biTree.postOrder();
    }
}
 
解释：假设先序数组A B D E C F 中序数组D B E A F C
 
 
已知中序后序求先序
 
public class BinaryTree2 {
    private Node root;

    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node localroot) {
        if(localroot!=null){
            System.out.print(localroot.data+" ");
            preOrder(localroot.left);
            preOrder(localroot.right);
        }
    }

    public void initTree(int[] inOrder,int[] postOrder){
        this.root=initTree(inOrder,0,inOrder.length-1,postOrder,0,postOrder.length-1);
    }

    private Node initTree(int[] inOrder, int start1, int end1, int[] postOrder, int start2, int end2) {
        if(start1>end1||start2>end2){
            return null;
        }
        int rootdata=postOrder[end2];
        Node head=new Node(rootdata);
        int rootindex=findIndexInArray(inOrder,rootdata,start1,end1);
        int offset=rootindex-1-start1;
        Node left=initTree(inOrder,start1,start1+offset,postOrder,start2,start2+offset);
        Node right=initTree(inOrder,rootindex+1,end1,postOrder,start2+offset+1,end2-1);
        head.left=left;
        head.right=right;
        return head;
    }

    public int  findIndexInArray(int[] a,int x,int begin,int end){
        for (int i = begin; i <=end; i++) {
            if(a[i]==x){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        BinaryTree2 biTree=new BinaryTree2();
        int[] inorder={1,2,3,4,5,6,7,7,8,9};
        int[] postOrder={1,3,5,6,4,7,7,9,8,2 };
        biTree.initTree(inorder,postOrder);
        System.out.println("先序遍历");
        biTree.preOrder();
    }
}
 
解释同上。。。。。。

 
 
简单易忘~~~
 
 
已知先序中序求后序:
 
 
 
  
/*
    已知先序和中序 求后序
 */

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

#define maxn 1010

int pre[maxn], in[maxn], post[maxn];
int n;
int cnt;

int ask_root(int len, int root_num, int in[]) { //在当前的子树立找根节点
    for (int i=0; i<len; ++i) {
        if (in[i] == root_num)
            return i;
    }
    return -1;
}

void askPost(int len, int pre[], int in[]) { // 当前先序和中序序列的长度
    int root_id = ask_root(len, pre[0], in);
    if (root_id < 0) return;
    askPost(root_id, pre+1, in); // 递归到当前根节点的左子树
    askPost(len-root_id-1, pre+root_id+1, in+root_id+1); // 递归到当前根节点的右子树
    post[cnt++] = pre[0]; // 递归完左子树和右子树之后 剩下了最左的叶子结点 加入后序序列中
}

int main() {
    while(cin >> n) {
         cnt = 0;
         for (int i=0; i<n; ++i) { // 输入先序序列
            cin >> pre[i];
         }
         for (int i=0; i<n; ++i) { // 输入中序序列
            cin >> in[i];
         }

         askPost(n, pre, in); //

         for (int i=0; i<n; ++i) {
            cout << post[i] << endl;
         }
    }
    return 0;
}
 
 
 
 
　　
 
 
已知中序后序求先序：
 
 
 
  
/*
 已知二叉树的中序和后序 求其先序
 */

#include <stdio.h>
#include <string.h>
#include <iostream>
#define maxn 1010
using namespace std;

int pre[maxn], in[maxn], post[maxn];
int n;
int cnt;

int ask_root(int len, int root, int in[]) {
    for (int i=0; i<len; ++i) {
        if (in[i] == root)
            return i;
    }
    return -1;
}

void askPre(int len, int in[], int post[]) {
    int root_id = ask_root(len, post[len-1], in);

   // cout << root_id << "===\n";
    if (root_id == -1) return;
    pre[cnt++] = post[len-1]; // 将当前根节点加入到先序序列中
    askPre(root_id, in, post); // 递归到左子树
    askPre(len-root_id-1, in+root_id+1, post+root_id); //递归到右子树
}


int main() {
    while(cin >> n) {
        cnt = 0;
        for (int i=0; i<n; ++i) {
            cin >> in[i]; // 输入中序
        }
        for (int i=0; i<n; ++i) {
            cin >> post[i]; // 输入后序
        }

        askPre(n, in, post);

        for (int i=0; i<n; ++i) {
            cout << pre[i] << endl;
        }
    }
    return 0;
}
 
 
 
 
　　
 
 
转载于:https://www.cnblogs.com/icode-girl/p/5289167.html

 思路：
 一开始过度关注这个堆栈的过程，半天get不到思路
 后来尝试着写了一下出栈序列，发现正好是中序遍历结果，那么这道题就转换成已知先序中序求后序的题
 对于这道题，入栈序列：123456；出栈序列：324165
 根据这个建树然后后序遍历即可
 
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct node{
  int data;
  node *left,*right;
};
vector<int> pre,in,post;
node* create(int prel,int prer,int inl,int inr)
{
	if(prel>prer)return NULL; 
	node* root=new node;
	root->data=pre[prel];
	int k;
	for(k=inl;k<=inr;k++)
	{
		if(in[k]==pre[prel])break;
	}
	root->left=create(prel+1,prel+k-inl,inl,k-1);
	root->right=create(prel+k-inl+1,prer,k+1,inr);
	return root;
}
void postorder(node* root)
{
	if(root==NULL)return;
	postorder(root->left);
	postorder(root->right);
	post.push_back(root->data);
}
int main()
{
  int n,temp;
  string str;
  stack<int> s;
  cin>>n;
  for(int i=0;i<2*n;i++)
  {
    cin>>str;
    if(str=="Push")
    {
      cin>>temp;
      pre.push_back(temp);
      s.push(temp);
    }
    else
    {
      in.push_back(s.top());
      s.pop();
    }
  }
    node* rot=create(0,n-1,0,n-1);
    postorder(rot);
    for(int i=0;i<n;i++)
    {
    	cout<<post[i];
    	if(i!=n-1)cout<<" ";
    	else cout<<endl;
    }
    return 0;
}