第一部分：
链表
直接上代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39// Definition for singly-linked list. public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } private static ListNode createLinkedList(int[] arr) {// 将输入的数组输入到链表中 if (arr.length == 0) { return null; } ListNode head = new ListNode(arr[0]); ListNode current = head; for (int i = 1; i < arr.length; i++) {// 过程 current.next = new ListNode(arr[i]); current = current.next; } return head; } private static void printLinkedList(ListNode head) {// 将链表结果打印 ListNode current = head; while (current != null) { System.out.printf("%d -> ", current.val); current = current.next; } System.out.println("NULL"); } public static void main(String[] args) { int[] x = { 1, 2, 3, 4, 5, 6 }; ListNode list = createLinkedList(x); printLinkedList(list); }
打印出来的结果是：
树
直接上代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91// Definition for a binary tree node. public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static TreeNode constructTree(Integer[] nums){ if (nums.length == 0) return new TreeNode(0); Deque<TreeNode> nodeQueue = new LinkedList<>(); // 创建一个根节点 TreeNode root = new TreeNode(nums[0]); nodeQueue.offer(root); TreeNode cur; // 记录当前行节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2） int lineNodeNum = 2; // 记录当前行中数字在数组中的开始位置 int startIndex = 1; // 记录数组中剩余的元素的数量 int restLength = nums.length - 1; while(restLength > 0) { // 只有最后一行可以不满，其余行必须是满的 // // 若输入的数组的数量是错误的，直接跳出程序 // if (restLength < lineNodeNum) { // System.out.println("Wrong Input!"); // return new TreeNode(0); // } for (int i = startIndex; i < startIndex + lineNodeNum; i = i + 2) { // 说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root if (i == nums.length) return root; cur = nodeQueue.poll(); if (nums[i] != null) { cur.left = new TreeNode(nums[i]); nodeQueue.offer(cur.left); } // 同上，说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root if (i + 1 == nums.length) return root; if (nums[i + 1] != null) { cur.right = new TreeNode(nums[i + 1]); nodeQueue.offer(cur.right); } } startIndex += lineNodeNum; restLength -= lineNodeNum; lineNodeNum = nodeQueue.size() * 2; } return root; } public static void preOrder(TreeNode root) {//前序排列 if (root == null) return; System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); } public static void midOrder(TreeNode root) {//中序排列 if (root == null) return; midOrder(root.left); System.out.print(root.val + " "); midOrder(root.right); } public static void aftOrder(TreeNode root) {//后序排列 if (root == null) return; aftOrder(root.left); aftOrder(root.right); System.out.print(root.val + " "); } public static void main(String[] args) { Integer[] nums = {1,2,2,3,3,3,3}; TreeNode tree=constructTree(nums); System.out.println("先序遍历："); preOrder(tree); System.out.println(); System.out.println("中序遍历："); midOrder(tree); System.out.println(); System.out.println("后序遍历："); aftOrder(tree); System.out.println(); }
打印出来的结果是：
第二部分：
这段时间时不时地会在leetcode上做些题，最近做到的大部分是与树相关的题。由于是在本地的IDE上码代码，如果每次测试都要到leetcode上来测的话，不仅要选中复制粘贴一遍，而且每次测试还要读一会条，一次两次还好，次数多了还是比较烦。而如果在本地的类内的main()函数里测试的话，每次构建一个树也比较麻烦，而且仅仅更换数值还好，若要更换树的结构，那工程量就有点大了。
所以在这里准备写一个创建树的函数来解决这个问题，后面做起题来效率也能高一些。
话不多说，下面先直接放上所用的代码：
1
2
3
4
5
6
7
8
9本例中所构建的树的结构 5 / 4 8 / / 11 13 4 / 7 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58package learning_java; import LeetCode.TreeNode; import java.util.Deque; import java.util.LinkedList; public class ConstructTree { public static TreeNode constructTree(Integer[] nums){ if (nums.length == 0) return new TreeNode(0); Deque<TreeNode> nodeQueue = new LinkedList<>(); // 创建一个根节点 TreeNode root = new TreeNode(nums[0]); nodeQueue.offer(root); TreeNode cur; // 记录当前行节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2） int lineNodeNum = 2; // 记录当前行中数字在数组中的开始位置 int startIndex = 1; // 记录数组中剩余的元素的数量 int restLength = nums.length - 1; while(restLength > 0) { // 只有最后一行可以不满，其余行必须是满的 // // 若输入的数组的数量是错误的，直接跳出程序 // if (restLength < lineNodeNum) { // System.out.println("Wrong Input!"); // return new TreeNode(0); // } for (int i = startIndex; i < startIndex + lineNodeNum; i = i + 2) { // 说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root if (i == nums.length) return root; cur = nodeQueue.poll(); if (nums[i] != null) { cur.left = new TreeNode(nums[i]); nodeQueue.offer(cur.left); } // 同上，说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root if (i + 1 == nums.length) return root; if (nums[i + 1] != null) { cur.right = new TreeNode(nums[i + 1]); nodeQueue.offer(cur.right); } } startIndex += lineNodeNum; restLength -= lineNodeNum; lineNodeNum = nodeQueue.size() * 2; } return root; } public static void main(String[] args) { Integer[] nums = {5,4,8,11,null,13,4,7,2,null,null,null,1}; TreeNode root = ConstructTree.constructTree(nums); System.out.println(root); } }
使用时，像上面main()方法中一样，只需要调用类内的静态方法constructTree(Integer[] nums)，输入的参量为一个整型的数组，数组中的元素是按层次遍历的二叉树的值（若某节点在下一层中的某个儿子或两个儿子为空，则在下一层的这一个或两个位置填null），与Leetcode中树的表示方法相同，即可以直接把Leetcode上的测试用例按它的形式拖过来直接使用。
简单解释一下所用的方法，核心思想是在每一层，用一个队列nodeQueue来存储该层的所有节点，然后用父节点的数量的两倍来遍历输入的数组（从上一层结束的地方开始），并从队列中取出（位于上一层的）对应的父节点（此时已从队列中删去，因为用的方法为poll()而不是peek()），对于每一个值，创建相应的子节点链接到父节点，并加入到队列中，依次不断循环，直到遍历完整个数组。
这里一个踩过的坑是，其中因为一部分数值为null，而如果用int基本类型的数组的话，数组内是不能用null的，因此这里用了int的包装类Integer的数组来作为传入的参数的声明。
最后，让我们测试一下我们的代码，测试用的树与上面一样，测试中我们采用先序遍历来进行输出，查看结果是否正确：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/* 用于测试的树，与上例中相同 5 / 4 8 / / 11 13 4 / 7 2 1 */ package learning_java.sortTry; import LeetCode.TreeNode; import learning_java.ConstructTree; public class ConstructTreeTest { public void preOrder(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); } public static void main(String[] args) { Integer[] nums = {5,4,8,11,null,13,4,7,2,null,null,null,1}; TreeNode root = ConstructTree.constructTree(nums); new ConstructTreeTest().preOrder(root); } }
测试结果：
1
25 4 11 7 2 8 13 4 1
可以看到，我们得到了一棵所需要的树。
更新
在实际使用中发现，leetcode中所给的case经常并不是标准的个数，最后一行往往是不满的，如
1
2
3
45 / 4
这样一棵树，给出的数组中仅有两个数字：[5, 4]，即最后一行中的末尾的null会被舍弃，因此，在我们的程序中，应在遍历过程中加入停止条件（更严谨的方式是保存判定错误输入的条件，并仅在树的最后一行的遍历过程中进行停止判定）。
第三部分：
平时无论是工作还是学习中，在写代码时，树总是一个非常常见的数据结构。在我们完成一棵树的构建之后，如果我们想要看这棵树的结构，不像数组或者List等数据结构，我们可以非常方便地用各种方式将其中的所有元素打印出来，对于树而言，这个过程要麻烦得多，我们可以用各种遍历方式得到这棵树的结构，但是终究还是不够直观。
不知大家有没有想过，如果我们可以按照树的结构，将其打印出来就好了，那么本文就是一种实现这个目标的思路以供参考。
引言
树的结构
在本文中所用的树的结构是leetcode上所用的树的结构，其定义如下：
1
2
3
4
5
6
7public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } }
如何方便地创建一个树的数据结构？
在下面贴的这篇博客中中有详细的讲解，基于Leetcode中树的编码方式，由一个数组直接得到一棵树。
如何创建一棵树
如何打印一棵树
在这里，我的总体思路是，用一个二维的字符串数组来储存每个位置应该打印什么样的输出。
首先，先确定树的形状。为了美观，我设定在最后一行的每个数字之间的间隔为3个空格，而在之上的每一层的间隔，有兴趣的同学可以自己推算一下，总之，越往上，间隔是越大的，而且是一个简单的线性增加的关系。
为了绘制出这样的形状，首先，我们需要获得树的层数（用一个简单的递归即可得到），根据树的层数，确定我们的二维数组的大小，即高度和宽度。之后，用先序遍历的方式，遍历树的每个节点，并进行相对应的写入操作。
更详细的解释可以看代码中的注释，当然，也可以根据下面TreeOperationTest.java中的demo直接在自己的代码中调用这个方法来检查自己的树。
话不多说，直接贴上所用的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79// TreeOperation.java public class TreeOperation { /* 树的结构示例： 1 / 2 3 / / 4 5 6 7 */ // 用于获得树的层数 public static int getTreeDepth(TreeNode root) { return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right))); } private static void writeArray(TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) { // 保证输入的树不为空 if (currNode == null) return; // 先将当前节点保存到二维数组中 res[rowIndex][columnIndex] = String.valueOf(currNode.val); // 计算当前位于树的第几层 int currLevel = ((rowIndex + 1) / 2); // 若到了最后一层，则返回 if (currLevel == treeDepth) return; // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔） int gap = treeDepth - currLevel - 1; // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值 if (currNode.left != null) { res[rowIndex + 1][columnIndex - gap] = "/"; writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth); } // 对右儿子进行判断，若有右儿子，则记录相应的""与右儿子的值 if (currNode.right != null) { res[rowIndex + 1][columnIndex + gap] = "\"; writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth); } } public static void show(TreeNode root) { if (root == null) System.out.println("EMPTY!"); // 得到树的深度 int treeDepth = getTreeDepth(root); // 最后一行的宽度为2的（n - 1）次方乘3，再加1 // 作为整个二维数组的宽度 int arrayHeight = treeDepth * 2 - 1; int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1; // 用一个字符串数组来存储每个位置应显示的元素 String[][] res = new String[arrayHeight][arrayWidth]; // 对数组进行初始化，默认为一个空格 for (int i = 0; i < arrayHeight; i ++) { for (int j = 0; j < arrayWidth; j ++) { res[i][j] = " "; } } // 从根节点开始，递归处理整个树 // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0'); writeArray(root, 0, arrayWidth/ 2, res, treeDepth); // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可 for (String[] line: res) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < line.length; i ++) { sb.append(line[i]); if (line[i].length() > 1 && i <= line.length - 1) { i += line[i].length() > 4 ? 2: line[i].length() - 1; } } System.out.println(sb.toString()); } } }
接下来，是用于测试的程序，如果需要调用上面的方法，以下面的代码为demo即可。需要注意的一点是，其中构建树的代码为如何创建一棵树中的方法，需要将这些.java文件放在个包中（包括TreeNode.java），才可以正常使用。
1
2
3
4
5
6
7
8
9
10
11// // TreeOperationTest.java public class TreeOperatinTest { public static void main(String[] args) { Integer nums[] = { 1, 2, 3, 4, 5 ,6, 7 }; // 根据给定的数组创建一棵树 TreeNode root = ConstructTree.constructTree(nums); // 将刚刚创建的树打印出来 TreeOperation.show(root); } }
输出：
1
2
3
4
5
61 / 2 3 / / 4 5 6 7
可以看到，这里我们用了两行代码，便创建出了一棵我们需要的树，并且按照树的格式将一棵完整的树打印了出来。
当然，我们也可以换一棵树再来测试，我们就使用在这篇如何创建一棵树中的曾经使用过的例子再进行一次测试：
1
2
3
4
5
6
7
8public class TreeOperatinTest { public static void main(String[] args) { Integer nums[] = { 5,4,8,11,null,13,4,7,2,null,null,null,1 }; TreeNode root = ConstructTree.constructTree(nums); TreeOperation.show(root); } }
输出：
1
2
3
4
5
6
7
85 / 4 8 / / 11 13 4 / 7 2 1
可以看到，即使树并不完整， 且其中有超过1位的数字，依然可以正确地输出。
一点问题
由于本方法的思路是基于字符串的数组的，所以并不可能完美适配所有情况，比如当树的高度很高以后，可能看起来会很奇怪（?）。
还有一个问题就是，虽然已经做了自适应处理，但是，如果出现超过5位的数字（比如123123），其所在的行可能会有一点向右的偏移，若偏的不多，是不影响观察的，但若偏的多了就。。。。不过这里已经做了处理，所以出现三位或者四位数的时候是没有问题的。
不过，在日常的应用中，应该是完全够用的，希望这段代码能为大家带来便利。
参考：
- Leetcode链表和树在IDEA中测试用例
- 从数组形式创建一棵树（用于leetcode测试）
- 按照树形结构直观地打印出一棵二叉树(Java)
- 按照树形结构直观地打印出一棵二叉树(Java)
最后
以上就是知性烧鹅最近收集整理的关于LeetCode如何构建链表和树的测试用例第一部分：第二部分：第三部分：参考：的全部内容，更多相关LeetCode如何构建链表和树内容请搜索靠谱客的其他文章。
发表评论 取消回复