LeetCode用数组建立二叉树
1.需求
在LeetCode上刷到二叉树相关的题目时，发现题目中都没法直接给出二叉树结构，而是给一个数组，现在需要利用这个数组构建起二叉树的结构。
2.分析
首先分析一下LeetCode上给的数组有什么规律，以110题平衡二叉树为例
这里不难看出数组里面的两个null，是9的两个子节点，为了清楚的指明树的结构（15、7是20的子节点而不是9的子节点），这里必须记录两个null。
同样的道理观察第二个例子，发现这个数组里面的两个null是前面2的子节点，但是最右侧的3却没有给出两个null的子节点。这是为什么呢？
3.结论：
首先给出的数组大致依据肯定是层序遍历，但是单纯一个层序遍历的数组肯定不能唯一声明一个二叉树，所以一定要做特殊处理，就是把一些必要的null塞进数组，但是到底哪些null必须写进去，这里我根据我构建二叉树的代码，总结了几点要求。
（1）.除最底层外的结点外，仅有单个子节点或者没有子结点的，必须把子节点记为null写入数组。（参见例1）
（2）.如果数组最后两位是null，则省略。
比如例3，把右侧结点3的子节点记为null的话，数组为 [1,2,2,3,3,null,null,4,4,null,null]，最后两位是null，所以省略。
至于省略的原因，在构建二叉树的代码中，空结点是不入队列的，而最后两个结点时null的话也就意味着处理完前面地结点后，队列就空了，没有需要处理的了，所以可以省略。
（3）.不要补全成为完全二叉树
如果把例3这样补全成完全二叉树，数组[1,2,2,3,3,null,null,4,4,null,null,null,null,null,null] ，这样当然可以唯一声明一个二叉树，但是对于一些斜二叉树来说，这样做很浪费空间，完全可以优化。况且代码中空结点不入队列，这样做的话需要给空结点赋予空的左右结点，是错误的。
4.原理
这里使用一个先进先出的结构队列queue，先将头结点入队，每次将队头结点出队，就将后面两个结点入队，这两个入队的就是刚才出队结点的左右子节点。
5.代码
最后给出代码段
#include <vector>
#include <string>
#include <queue>
using namespace std;
//二叉树结点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() :val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) :val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) :val(x), left(left), right(right) {}
};
TreeNode* createBinaryTree(vector<string> nodes) {
int len = nodes.size();
if (len == 0) {
return NULL;
}
if (nodes[0] == "null") {
return nullptr;
}
TreeNode* root;
//建立结点队列并将根节点入队
queue<TreeNode*> nodesQue;
root = new TreeNode(stoi(nodes[0]));
nodesQue.push(root);
//loc遍历数组，每次取两个结点
for (int loc = 1; loc < len; loc = loc + 2) {
//获取结点并出队
TreeNode* node = nodesQue.front();
nodesQue.pop();
//获取队头结点的左右结点
string left = nodes[loc];
string right = nodes[loc + 1];
//赋予左右结点
if (left == "null") {
node->left = nullptr;
}
else {
node->left = new TreeNode(stoi(left));
nodesQue.push(node->left);
}
if (right == "null") {
node->right = nullptr;
}
else {
node->right = new TreeNode(stoi(right));
nodesQue.push(node->right);
}
}
return root;
}