题目描述
二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历
其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问
根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子
树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定
前序遍历与中序遍历能够唯一确定后序遍历）。

输入
两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出
输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。

样例输入
ABC
BAC
FDXEAG
XDEFAG

样例输出
BCA
XEDGAF

代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Bitree{
    char data;
    struct Bitree * lchild;
    struct Bitree * rchild;
} * BiTree,BiNode;

void CreateBiTree(BiTree T,char * preOrder,char * inOrder,int preLow,int preHigh,int inLow,int inHigh){
    T->lchild = NULL;
    T->rchild = NULL;
    T->data = preOrder[preLow];
    if(preLow == preHigh) return;
    int i = inLow;
    while(inOrder[i] != preOrder[preLow]) i ++;
    if(i - 1 >= inLow){
        T->lchild = (BiTree)malloc(sizeof(BiNode));
        CreateBiTree(T->lchild, preOrder, inOrder, preLow + 1, preLow + i - inLow, inLow, i - 1);
    }
    if(inHigh >= i + 1){
        T->rchild = (BiTree)malloc(sizeof(BiNode));
        CreateBiTree(T->rchild, preOrder, inOrder, preLow + i - inLow + 1, preHigh, i + 1, inHigh);

    }
}
void PreOrder(BiTree T){
    if(T != NULL){
        printf("%c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void InOrder(BiTree T){
    if(T != NULL){
        InOrder(T->lchild);
        printf("%c",T->data);
        InOrder(T->rchild);
    }
}

void PostOrder(BiTree T){
    if(T != NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%c",T->data);
    }
}

int main(int argc, const char * argv[]) {
    char preOrder[26],inOrder[26];
    while(scanf("%s", preOrder) != EOF){
        scanf("%s", inOrder);
        int n = strlen(preOrder);
        BiTree T = (BiTree)malloc(sizeof(BiNode));
        T->lchild = NULL;
        T->rchild = NULL;
        CreateBiTree(T, preOrder, inOrder, 0, n - 1, 0, n - 1);
        PostOrder(T);
        printf("\n");
    }
    return 0;
}


总结
注意递归跳出条件
注意树的分配空间的时候，一定要防止断链
注意递归的使用条件

题目1078：二叉树遍历
题目描述：
二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历(提示：给定前序遍历与中序遍历能够唯一确定后序遍历)。
输入：
两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
输出：
输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。
样例
输入：
ABC
BAC
FDXEAG
XDEFAG
样例输出：
BCA
XEDGAF
来源：
2006年清华大学计算机研究生机试真题
--------------------------------------------------------
解析
由前序遍历和中序遍历求后序遍历，这要求考生对三种遍历方式都有掌握。这里要用到前序遍历的根结点第一个被取出，而中序遍历的左子树在根结点之前取出、右子树在根结点之后取出，这两个性质。
C++实现如下
#include 
#include 
//1078：二叉树遍历
using namespace std;
//结点类
struct Node
{
Node * lchild;
Node * rchild;
char c;
};
//重建后续排序二叉树
Node * rebuild(string s1, string s2)
{
//建立根结点
Node * t=NULL;//一定要初始化为NULL，不然报错
if(s1.size()>0){
t=new Node;
t->c=s1[0];
t->lchild=NULL;
t->rchild=NULL;
}
if(s1.size()>1){
//寻找根结点在中序遍历中的位置
int root;
for(int i=0; i
if(s2[i]==t->c){
root=i;
break;
}
}
//左子树重建
string qianxu_left=s1.substr(1, root); //注意substr的用法，第二个参数是子字符串长度
string zhongxu_left=s2.substr(0, root);
t->lchild=rebuild(qianxu_left, zhongxu_left);
//右子树重建
string qianxu_right=s1.substr(root+1, s1.size()-root-1);
string zhongxu_right=s2.substr(root+1, s2.size()-root-1);
t->rchild=rebuild(qianxu_right, zhongxu_right);
}
return t;
}
//后序遍历：左右根
void houxu(Node * t)
{
//左子树非空，遍历左子树
if(t->lchild!=NULL)
houxu(t->lchild);
//右子树非空，遍历右子树
if(t->rchild!=NULL)
houxu(t->rchild);
//取出该结点的值
cout<c;
}
int main()
{
string s1, s2;
while(cin>>s1>>s2){
Node * t=rebuild(s1, s2);
houxu(t);
cout<
}
return 0;
}运行结果
Accepted 内存：1520KB  代码长度：1465B  耗时：10MS

先序遍历&中序遍历

递归做法： 

递归做法比较容易理解，先在先序遍历中确定第一个点，这个点一定是根节点，然后在中序遍历中找到这个点的位置，那么这个位置之前的都是左子树，后边的都是右子树，然后分别递归。

class Solution {
public:
    int start = 0;
    TreeNode* build(vector<int>& pre,vector<int>& in, int ps,int pe, int is, int ie){
        if (ps>=pe)
            return NULL;
        int val = pre[ps];
        TreeNode* root = new TreeNode(val);
        int pos;
        for (int i=is;i<ie;i++){
            if (in[i]==val) {
                pos=i;
                break;
            }
        }
        root->left = build(pre,in,ps+1,ps+pos-is+1,is,pos);
        root->right= build(pre,in,pe-ie+pos+1,pe,pos+1,ie);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        return build(preorder,inorder,0,preorder.size(),0,inorder.size());
    }
};

非递归： 

非递归的做法有些不好理解，核心思想有两点： 

1 从先序遍历序列的头部开始从左向右访问，用一个栈保存访问过的节点，每次都要判断栈顶元素是否等于中序遍历的当前节点。

2 如果相等，说明栈顶节点左子树遍历完毕，那么接下来的节点应该是前驱节点的右节点，标志位置1。如果不相等，那么先序遍历的下一个节点依然是前驱节点的左节点或右节点，需要根据标志位确定。

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        stack<TreeNode*> st;
        int n = int(preorder.size());
        if (n == 0) return NULL;
        int i = 1, j = 0;
        TreeNode* root = new TreeNode(preorder[0]);
        bool flag = 0;
        TreeNode* pre = root;
        st.push(root);
        while (i < n){
            if (!st.empty() && st.top() -> val == inorder[j]){
                pre = st.top();
                st.pop();
                flag = 1;
                j++;
            }
            else if (flag){
                pre -> right = new TreeNode(preorder[i++]);
                pre = pre -> right;
                st.push(pre);
                flag = 0;
            }
            else{
                pre -> left = new TreeNode(preorder[i++]);
                pre = pre -> left;
                st.push(pre);
            }
        }
        return root;
    }

中序遍历&后序遍历 

基本类似，区别是从后向前遍历后序序列 

递归：



class Solution {
public:
    int find(vector<int> inorder, int v){
        for (int i = 0; i < inorder.size(); ++i){
            if (inorder[i] == v) return i;
        }
        return -1;
    }
    TreeNode* build(vector<int>& inorder, vector<int>& postorder, int s1, int e1, int s2, int e2){
        if (s1 > e1) return NULL;
        else{
            int v = postorder[e2];
            int index = find(inorder, v);
            TreeNode* root = new TreeNode(v);
            root -> left = build(inorder,postorder,s1,index-1,s2,s2+index-1-s1);
            root -> right = build(inorder,postorder,index+1,e1,s2+index-s1,e2-1);
            return root;
        }

    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        if (n == 0) return NULL;
        return build(inorder,postorder,0,n-1,0,n-1);
    }
};

非递归



TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        if (n == 0) return NULL;
        int i = n-1, j = n-2;
        TreeNode* root = new TreeNode(postorder[n-1]);
        TreeNode* pre = root;
        stack<TreeNode*> st;
        st.push(root);
        bool flag = 0;
        while (i >= 0){
            if (!st.empty() && st.top() -> val == inorder[i]){
                pre = st.top();
                st.pop();
                i--;
                flag = true;
            }else if (flag){
                pre -> left = new TreeNode(postorder[j--]);
                pre = pre -> left;
                st.push(pre);
                flag = 0;
            }else{
                pre -> right = new TreeNode(postorder[j--]);
                pre = pre -> right;
                st.push(pre);
            }
        }
        return root;
    }

由中序遍历和后序遍历重建二叉树

中序遍历中，根节点总是位于左右子树中间，将左右子树分开。

后序遍历中，根节点总是在左右子树之后。


重建算法：

现在说一下重建根节点的过程，其他节点可以递归建立。

由后序遍历定义可知，后序遍历序列的最后一个元素必定是整个树的根节点，这样就确定了根节点。

由中序遍历定义可知，在中序遍历中查找根节点，可以确定根节点在中序遍历序列中位置，这样就可以将中序遍历序列分为左右子树，一旦确定左右子树，左右子树的长度也就确定了，根据左右子树的长度，在后序遍历序列中，可以确定左右子树的根节点，这样递归下去既可以确定整个树。



# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, post, tin):
        # write code here
        if len(post) == 0 or len(tin) == 0:
            return None
        root = TreeNode(post[-1])
        # 获取根节点在中序遍历中的位置
        i = tin.index(post[-1])
        """
        注意下面四个参数，可以根据测试样例推导出来
        i为根节点
        post[0 : i]
        i结点前面的是左子树的结点所以参数如上
        tin[0 : i]
        同上，i结点前面的为左子树，可以观察测试数据
        post[i : -1]
        根节点在最后一位，右子树的结点为从i开始到-1，不包括最后一个结点
        tin[i + 1 : ] 
        中序遍历中i结点为根节点，i结点后面的为右子树的结点
        """
        # 遍历左子树
        root.left = self.reConstructBinaryTree(post[0 : i], tin[0 : i])
        # 遍历右子树
        root.right = self.reConstructBinaryTree(post[i : -1], tin[i + 1 : ])

        return root

if __name__ == "__main__":
    a = Solution()
    post_order = [7, 4, 2, 5, 8, 6, 3, 1] # 后序遍历
    mid_order =  [4, 7, 2, 1, 5, 3, 8, 6] # 中序遍历
    root = a.reConstructBinaryTree(post_order, mid_order)
    print root.val
    print root.left.val
    print root.right.val
    print root.left.left.val
    print root.left.left.right.val
    print root.right.right.left.val
    print root.right.left.val