算例一

• 题目描述

• 解题思路

①遍历二叉树思路：前序的第一个为根，据此可以找到中序中根的位置，前面是左子树，后面是右子树，同时获得左右子树的结点个数，返回到前序中也可以分离左右子树；重复操作直至左右子树为空。

• 解题代码

#include <stdio.h>
#include <string.h>
struct Node
{ //树结点结构体
	Node *lchild; //左儿子指针
	Node *rchild; //右儿子指针
	char c; //结点字符信息
}Tree[50]; //静态内存分配数组
int loc; //静态数组中已经分配的结点个数
Node *creat() { //申请一个结点空间,返回指向其的指针
	Tree[loc].lchild = Tree[loc].rchild = NULL; //初始化左右儿子为空
	return &Tree[loc++]; //返回指针,且loc累加
}
char str1[30], str2[30]; //保存前序和中序遍历结果字符串
void postOrder(Node * T) { //后序遍历
	if (T->lchild != NULL) { //若左子树不为空
		postOrder(T->lchild); //递归遍历其左子树
	}
	if (T->rchild != NULL) { //若右子树不为空
		postOrder(T->rchild); //递归遍历其右子树
	}
	printf("%c", T->c); //遍历该结点,输出其字符信息
}
Node *build(int s1, int e1, int s2, int e2) { //由字符串的前序遍历和中序遍历还原树, 并返回其根节点, 其中前序遍历结果为由str1[s1]到str2[e1]，中序遍历结果为str2[s2]到str2[e2]
	Node* ret = creat(); //为该树根节点申请空间
	ret->c = str1[s1]; //该结点字符为前序遍历中第一个字符
	int rootIdx;
	for (int i = s2;i <= e2;i++)
	{// 查找该根节点字符在中序遍历中的位置
		if (str2[i] == str1[s1]) {
			rootIdx = i;
			break;
		}
	}
	if (rootIdx != s2) { //若左子树不为空
		ret->lchil d = build(s1 + 1, s1 + (rootIdx - s2), s2, rootIdx - 1); //
		递归还原其左子树
	}
	if (rootIdx != e2) { //若右子树不为空
		ret->rchild = build(s1 + (rootIdx - s2) + 1, e1, rootIdx + 1, e2); //
		递归还原其右子树
	}
	return ret; //返回根节点指针
}
int main() {
	while (scanf("%s", str1) != EOF) {
		scanf("%s", str2); //输入
		loc = 0; //初始化静态内存空间中已经使用结点个数为0
		int L1 = strlen(str1);
		int L2 = strlen(str2); //计算两个字符串长度
		Node * T = build(0, L1 - 1, 0, L2 - 1); //还原整棵树,其根结点指针保存在T中
		postOrder(T); //后序遍历
		printf("\n"); //输出换行
	}
	return 0;
}

• 注意点

①代码中没有动态的申请内存空间，并在程序结束时释放这些空间。而是使用了静态数组，利用分配数组元素给相应的结点实现内存分配。这是对内存分配较为简单的实现方法，若读者对动态的申请和释放内存没有把握，或者对何时何地释放内存抱有疑惑，建议使用该较为保险的方法。

②后序遍历时候直接输出就好了，为什么要先存数组？？？【对自我灵魂的拷问】

③关于二叉树的其它考点，都与二叉树的性质有关，如每层的结点个数、确定结点个数的最小树高等，自己要掌握

⑦以上代码利用c实现，也可以利用stl的vector进行实现→

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */

    class Solution {
    public:
        struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
            int inlen=in.size();
            if(inlen==0)
                return NULL;
           
            vector<int> left_pre,right_pre,left_in,right_in;

            //创建根节点，根节点肯定是前序遍历的第一个数
            TreeNode* head=new TreeNode(pre[0]);
            //找到中序遍历根节点所在位置,存放于变量gen中
            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_in.push_back(in[i]);
                left_pre.push_back(pre[i+1]);//前序第一个为根节点
            }
 
            for(int i=gen+1;i<inlen;i++)
            {
                right_in.push_back(in[i]);
                right_pre.push_back(pre[i]);
            }
 
            //和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树
            //递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
           head->left=reConstructBinaryTree(left_pre,left_in);
           head->right=reConstructBinaryTree(right_pre,right_in);
           return head;
        }
    };

注意点

①注意原始根的创建方式

②前者用全局变量loc来确定左右子树的数组Idx数，后者用vector的方式实现了数组的增加，看起来比前者方便点