简单来说就是在每次尝试第 i 行新的摆法、并且递归的 trying 了它的下一行之后，需要还原第 i 行的状态。输出棋盘则可以直接在每次判断是可行解之后w

#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;
}