已知树的两种遍历方式（包含中序）建立树的代码

知道中序遍历 + 后序 / 先序遍历 得出树的结构

已知后序和中序输出前序

void pre(int root, int start , int end){ if(start > end) return; int i = start; while(i < end && in[i] != post[root]) i++;// 抓根宝 pre(root - 1 - end + i,start, i - 1); pre(root - 1, i + 1 , end);}

左子树在后序中的根结点为root - (end - i + 1) 即为当前根结点 - （右子树的个数 + 1)。左子树在中序中的起点为start,末尾点为i - 1。右子树更容易理解。

void post(int root, int start, int end){ if(start > end) return; int i = start; while(i < end && in[i] != pre[root]) i++;// 抓根宝 post(root + 1, start , i - 1); post(root + i - start + 1 , i + 1 , end);}

TreeNode* buildTree(int root, int start, int end) { if(start > end) return NULL; int i = start; while(i < end && in[i] != pre[root]) i++; TreeNode* t = new TreeNode(); t->left = buildTree(root + 1, start, i - 1); t->right = buildTree(root + 1 + i - start, i + 1, end); t->data = pre[root]; return t;}

建树代码

分析：同理 前序遍历的左右子树根分别在root + 1 和 root + (i - start) + 1上分解成子问题即可

// 如果是层序遍历需要重新建树 只要在遍历函数中加上一个变量index,表示当前根结点在二叉树中所对应的下标

例题：https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072

// 参考博文https://www.liuchuo.net/archives/2087
讲解视频可以参考浙大数据结构网课遍历的应用部分