如何根据数组创建二叉树？
By Long Luo
之前的如何根据数组或者字符串创建链表？ 详述了Leetcode 中链表 相关算法题的测试方法。在Leetcode中关于树 的算法题中，很多树的题目，测试用例都是一个数组，比如102. 二叉树的层序遍历 中所示：1
2
3
4
5
6给定二叉树: [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
那么问题来了，如何根据数组构造一颗树呢？ 为了加快刷题，我们需要一个工具来实现构造树和打印树结构这2个问题。
树
树是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n(n>0)个有限节点组成一个具有层次关系的集合。
如上图所示，把它叫做「树」是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树具有以下的特点： - 每个节点都只有有限个子节点或无子节点； - 没有父节点的节点称为根节点； - 每一个非根节点有且只有一个父节点； - 除了根节点外，每个子节点可以分为多个不相交的子树； - 树里面没有环路。
当我们完成一棵树的构建之后，虽然我们已经有树的前序、中序和后序遍历这种可以遍历树，但是如果我们如上图一样展示这棵树的结构，如何才能直观地打印出来呢？
如何打印一棵树？
这里我们借用Leetcode中二叉树的数据结构定义：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/**
* Definition for a binary tree node.
*/
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
this.val = x;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
思路
树的展示方式有2种，水平展示和竖直展示。竖直展示比较直观，水平展示更适合用于节点元素大小长短不一致的情况，Linux下展示文件结构就是水平展示。
