LeetCode构建链表和树的测试用例
背景：当Leetcode题目需要本地IDE调试时，构建链表和树结构会比较繁琐，刚好对一些资料进行整理，本地运行通过。
IDE.jpegTable of Contents
- 单链表(LinkedList)测试用例生成
- 树(BinaryTree)的测试用例生成
- 树(BinaryTree)结构的打印
单链表(LinkedList)测试用例生成
应用：Leetcode148 排序链表
测试用例生成代码：
代码语言：txt复制package com.haowang.TestUtils;
public class UseCase_LinkedList {
public static class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
next = null;
}
public ListNode(ListNode node) {
this.val = node.val;
this.next = node.next;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public void setVal(int val) {
this.val = val;
}
public int getVal() {
return this.val;
}
public ListNode getNext() {
return this.next;
}
public void setNext(ListNode node) {
this.next = node;
}
}
public 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;
}
public 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);
}
}树(BinaryTree)的测试用例生成
二叉树（BinaryTree）的定义，构造树的测试用例生成，先序遍历、中序遍历和后序遍历。
代码语言：txt复制package com.haowang.TestUtils;
import java.util.Deque;
import java.util.LinkedList;
public class UseCase_BinaryTree {
// Definition for a binary tree node.
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
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); //offer()添加元素
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); //offer()添加元素
}
// 同上，说明已经将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) {
System.out.println("n案例1");
Integer[] nums = {1, 2, 2, 3, 3, 3, 3};
TreeNode tree = constructTree(nums);
TreeOperation.show(tree);
System.out.println("先序遍历：");
preOrder(tree);
System.out.println();
System.out.println("中序遍历：");
midOrder(tree);
System.out.println();
System.out.println("后序遍历：");
aftOrder(tree);
System.out.println();
/**
用于测试的树，与上例中相同
5
/
4 8
/ /
11 13 4
/
7 2 1
*/
System.out.println("n案例2");
Integer[] nums2 = {5,4,8,11,null,13,4,7,2,null,null,null,1};
TreeNode tree2 = constructTree(nums2);
TreeOperation.show(tree2);
System.out.println("后序遍历：");
preOrder(tree2); // 预期结果：5 4 11 7 2 8 13 4 1
System.out.println();
// 将刚刚创建的树打印出来
// 调试打印树
System.out.println("n案例3");
Integer[] nums3 = { 1, 2, 3, 4, 5 ,6, 7 };
// 根据给定的数组创建一棵树
TreeNode tree3 = constructTree(nums3);
// 将刚刚创建的树打印出来
TreeOperation.show(tree3);
}
}树结构打印
代码语言：txt复制package com.haowang.TestUtils;
public class TreeOperation {
/*
树的结构示例：
1
/
2 3
/ /
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(UseCase_BinaryTree.TreeNode root) {
return root == null ? 0 : (1 Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}
private static void writeArray(UseCase_BinaryTree.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(UseCase_BinaryTree.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());
}
}
}参考资料
LeetCode如何构建链表和树的测试用例
