如何根据数组创建二叉树?
By Long Luo
之前的如何根据数组或者字符串创建链表? 详述了Leetcode 中链表 相关算法题的测试方法。在Leetcode中关于树 的算法题中,很多树的题目,测试用例都是一个数组,比如102. 二叉树的层序遍历 中所示:
1 | 给定二叉树: [3,9,20,null,null,15,7] |
那么问题来了,如何根据数组构造一颗树呢?
为了加快刷题,我们需要一个工具来实现构造树和打印树结构这2个问题。
树
树是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由 n(n>0)个有限节点组成一个具有层次关系的集合。
如上图所示,把它叫做「树」是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
树具有以下的特点:
- 每个节点都只有有限个子节点或无子节点;
- 没有父节点的节点称为根节点;
- 每一个非根节点有且只有一个父节点;
- 除了根节点外,每个子节点可以分为多个不相交的子树;
- 树里面没有环路。
当我们完成一棵树的构建之后,虽然我们已经有树的前序、中序和后序遍历这种可以遍历树,但是如果我们如上图一样展示这棵树的结构,如何才能直观地打印出来呢?
如何打印一棵树?
这里我们借用Leetcode中二叉树的数据结构定义:
1 | /** |
思路
树的展示方式有2种,水平展示和竖直展示。竖直展示比较直观,水平展示更适合用于节点元素大小长短不一致的情况,Linux下展示文件结构就是水平展示。
水平树
代码如下所示:
1 | public static int getTreeDepth(TreeNode root) { |
垂直树
代码如下所示:
1 | public static void printTree(TreeNode root) { |
从数组构建一棵二叉树
代码如下所示:
1 | public static TreeNode constructTree(Integer[] array) { |
测试
下面就来测试下代码吧:
1 | public static void main(String[] args) { |
输出如下所示:
1 | Tree: |
小结
通过上述,我们最终就完成了我们的任务。