在刷leetcode题目时，在刷LeetCode的时候，经常碰到树或二叉树模型的题目。为了调试方便，需要在本地IDE上实现对二叉树的创建。题目给出的是一个含有null的数组。
如：
[5,4,8,11,null,13,4,7,2,null,null,5,1]
首先我们需要创建一个数组。注意由于包含null值，因此肯定不能用int整型数组。由于Integer是引用类型，默认值为null，故可以创建一个Integer类型数组：
Integer[] arr = {5,4,8,11,null,13,4,7,2,null,null,5,1};
本文参考了这篇文章的思想：LeetCode(力扣)题目中二叉树的如何生成？根据给定顺序列表生成二叉树 。这里给出的是用python队列实现的二叉树创建。下面给出java实现的二叉树创建代码
static TreeNode createBT(Integer[] array){
if (array.length == 0){
return null;
}
// 创建第一个结点
TreeNode root = new TreeNode(array[0]);
Deque<TreeNode> deque = new LinkedList<>();
deque.addFirst(root);
// 遍历子结点的方向
boolean isLeft = true;
for (int i = 1; i < array.length; i++) {
// 取出队尾元素
TreeNode node = deque.getLast();
if (isLeft){
if (array[i]!=null){
node.left = new TreeNode(array[i]);
deque.addFirst(node.left);
}
isLeft = false;
}else{
if (array[i]!=null){
node.right = new TreeNode(array[i]);
deque.addFirst(node.right);
}
// 删除队尾元素
deque.removeLast();
isLeft = true;
}
}
return root;
}
由于遍历建树的过程中涉及到对队列尾部元素的查询和删除操作，所有使用的双端队列Deque。
注意：
网上常见的那种递归创建二叉树的算法(如下图所示)是有问题的。
static TreeNode createBT(int[] array, int index){
// 该算法有问题
TreeNode root = null;
if (index >=array.length||array[index] == -1){
return null;
}
root = new TreeNode(array[index]);
root.left = createBT(array,2*index+1);
root.right = createBT(array,2*index+2);
return root;
}
因为当index取值对应到的值为null时，程序会直接返回，结束本次递归。这可能会错过本应该在下一次递归时创建的树结点。如创建斜树：
[1,null,2,null,3]
3结点最终不会被创建。