写在前面：
通过前面两讲的学习，大家可能对二叉树有了比较深的感悟，但可能会发现一个小问题，我们在构建二叉树的时候都是一个个插入的，非常的不方便。那么这节课我们就来看看，如何通过输入一个数组来快速构建起一个二叉树。这里会介绍通过顺序数组、前序数组和后序数组如何构建二叉树。

完全二叉树的构建

在前面的学习中，我们知道了完全二叉树有一个非常 nice 的性质，它每个结点的左孩子在数组中的位置等于 2x ，右孩子等于 2x+1 。通过这个性质，我们可以快速的构建起一个二叉树。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left_node;
    Node *right_node;
};

int n;    //表示数组长度

//递归法构建二叉树
Node *creatTree(vector<int> nums, int index) {
    //判断是否为空
    if (nums[index] == '#')
        return NULL;

    //创建新结点
    Node *root = new Node;
    root->data = nums[index];

    //设置左右指针
    if (index * 2 <= n)
        root->left_node = creatTree(nums, index * 2);    //找到左孩子
    else
        root->left_node = NULL;
    if (index * 2 + 1 <= n)
        root->right_node = creatTree(nums, index * 2 + 1);    //找到右孩子
    else
        root->right_node = NULL;

    return root;
}

//非递归构建二叉树（利用栈）—— 前序遍历
void stackCreatTree(vector<int> nums) {
    int n = nums.size();
    stack<int> s;
    int index;    //记录遍历到第几个元素
    s.push(1);    //推入根结点，开始遍历
    while (!s.empty()) {
        index = s.top();
        s.pop();
        cout << nums[index] << " ";
        //先推入右孩子
        if (index * 2 + 1 < n && nums[index * 2 + 1] != '#')
            s.push(index * 2 + 1);
        //再推入左孩子，因为是栈结构，先进后出，而且前序遍历需要优先访问所有左子树，故只有一直放在栈顶才能先访问
        if (index * 2 < n && nums[index * 2] != '#')
            s.push(index * 2);
    }
    cout << endl;
}

//前序遍历
void PreOrderTraverse(Node *root) {
    if (root) {
        cout << root->data << " ";
        PreOrderTraverse(root->left_node);
        PreOrderTraverse(root->right_node);
    }
}

int main() {
    vector<int> nums = { '#', 1, 2, 3, 4, 5, '#', 6, '#', '#', 7, 8 };    //'#'指向空，并且从下标1开始存数据
    n = nums.size();
    Node *root = creatTree(nums, 1);
    PreOrderTraverse(root);
    cout << endl;
    stackCreatTree(nums);
    return 0;
}

根据前序和后序数组构建二叉树

除了给定一个顺序存储的数组外，还可能会给定前序遍历的结果，让你构建出二叉树。这里的操作和上面比较类似，但区别是我们获取结点的左右孩子的方式变了，上面我们是根据完全二叉树的性质。
（1）这里我们可以根据前序遍历的性质，也就是遍历结果遵循 根结点 | 左子树 | 右子树 的结果。所以，我们直接可以用一个全局变量下标来记录我们遍历的位置，从头往后遍历，每次都加 1 ，这样就可以连起来了。
（2）同样，后序遍历结果是遵循 左子树 | 右子树 | 根结点 的结果。所以，我们可以从最后一个元素开始往前遍历，每次都减 1 ，同样可以构建出来。

这里我们不用去判断下标是否超过数组长度，因为给定的数组是一定满足要求的即左子树右子树是否为空直接看'#'就可以。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left_node;
    Node *right_node;
};

int n;    //表示数组长度
int index;    //表示遍历到的下标

//前序数组创建二叉树

Node *prevCreatTree(vector<int> nums) {
    //判断是否为空
    if (nums[index] == '#') {
        index++;
        return NULL;
    }

    //创建结点
    Node *root = new Node;
    root->data = nums[index++];
    root->left_node = prevCreatTree(nums);
    root->right_node = prevCreatTree(nums);

    return root;
}

//后序数组创建二叉树
int cnt;
Node *backCreatTree(vector<int> nums) {
    if (nums[cnt] == '#') {
        cnt--;
        return NULL;
    }
    Node *root = new Node;
    root->data = nums[cnt--];
    root->right_node = backCreatTree(nums);
    root->left_node = backCreatTree(nums);
    return root;
}

//中序遍历
void InOrderTraverse(Node *root) {
    if (root) {
        InOrderTraverse(root->left_node);
        cout << root->data << " ";
        InOrderTraverse(root->right_node);
    }
}


int main() {
    //'#'指向空
    vector<int> nums1 = { 1, 2, 3, '#', '#', 4, '#', '#', 5, '#', '#' };
    vector<int> nums2 = {'#', '#', 3, '#', '#', 4, 2, '#', '#', 5, 1};
    index = 0;    //初始化下标
    Node *prev_root = prevCreatTree(nums1);
    InOrderTraverse(prev_root);
    cout << endl;
    cnt = nums2.size() - 1;
    Node *back_root = backCreatTree(nums2);
    InOrderTraverse(back_root);
    return 0;
}

如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~