#include <iostream> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; TreeNode * rebin(vector<int> pre, vector<int> in) { // 首先看看有米有东西吧 // 一个元素都没有的话 // 这个二叉树就只有一个NULL节点 // 直接返回即可w if (pre.size() == 0) return nullptr; // 根据前序遍历的定义 根节点一定在前序遍历结果的第一个位置上 // 而中序遍历的话 根结点必然需要等到它的左子树都输出完才会出现 // 利用这一点我们分开左右子树 int root_value = pre[0]; TreeNode * root = new TreeNode(root_value); // 找到根节点在中序遍历里的下标 // 以此分开左右子树 int root_index_of_in = 0; for (int i = 0; i < in.size(); i++) { if (in[i] == root_value) { root_index_of_in = i; break; } } // 分开左右子树 // 按原始的顺序分别保存左右子树的前序遍历和中序遍历 vector<int> left_pre, left_in, right_pre, right_in; // 先是左子树 for (int i = 0; i < root_index_of_in; i++) { // 这里需要+1 // 因为前序遍历的话 第一个元素是根节点 // 所以需要跳过当前(下标为0)的这个元素 left_pre.emplace_back(pre[i+1]); left_in.emplace_back(in[i]); } // 然后是右子树 for (int i = root_index_of_in + 1; i < in.size(); i++) { right_pre.emplace_back(pre[i]); right_in.emplace_back(in[i]); } // 既然左右子树的前序遍历和中序遍历都有了 // 和我们一开始拿到的初始条件很相似吧~ // 那么递归吧w root->left = rebin(left_pre, left_in); root->right = rebin(right_pre, right_in); return root; } // 三种遍历方式~/ typedef enum { PRE_ORDER, IN_ORDER, POST_ORDER, } TreeTraversal; void print_with_order(TreeNode * root, TreeTraversal order) { // 如果根节点是空的 // 那啥都不用说直接返回吧 if (root == nullptr) return; // 看看使用什么序来遍历 // 本质上仅仅只是输出当前root节点的位置不一样 if (order == PRE_ORDER) { cout << root->val << ' '; print_with_order(root->left, order); print_with_order(root->right, order); } else if (order == IN_ORDER) { print_with_order(root->left, order); cout << root->val << ' '; print_with_order(root->right, order); } else { print_with_order(root->left, order); print_with_order(root->right, order); cout << root->val << ' '; } } int main(int argc, const char * argv[]) { vector<int> pre = {1,2,4,7,3,5,6,8}; vector<int> in = {4,7,2,1,5,3,8,6}; TreeNode * head = rebin(pre, in); // 用构建好的树输出前序和中序遍历来验证~ cout << "pre: "; print_with_order(head, PRE_ORDER); cout << endl; cout << "in: "; print_with_order(head, IN_ORDER); cout << endl; }