前言
文章最后附上的完整代码，可以放到项目里做处理TreeNode（树）结构的工具类，包括字符串转TreeNode，和可视化打印TreeNode。
平时无论是工作还是学习中，在写代码时，树总是一个非常常见的数据结构。在我们完成一棵树的构建之后，如果我们想要看这棵树的结构，不像数组或者List等数据结构，我们可以非常方便地用各种方式将其中的所有元素打印出来，对于树而言，这个过程要麻烦得多，我们可以用各种遍历方式得到这棵树的结构，但是终究还是不够直观。
不知大家有没有想过，如果我们可以按照树的结构，将其打印出来就好了，那么本文就是一种实现这个目标的思路以供参考。
我是在做leetcode的 [236]二叉树的最近公共祖先 Medium 2023-02-13 185 时写的此文章，下面就用这道题目做实例。
1 效果图
引入文章结尾的工具类之后，生成和打印TreeNode，只需要
三行代码：
public class P236_LowestCommonAncestorOfABinaryTree{
public static void main(String[] args) {
String s = "[3,5,1,6,2,0,8,null,null,7,4]";
TreeNode treeNode = TreeNode.mkTree(s);
TreeNode.show(treeNode);
}
}
效果图：
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
2 树的结构
在本文中所用的树的结构是leetcode上所用的树的结构，其定义如下：
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
3 如何方便地创建一个树的数据结构？
leetcode里总是通过"[3,9,20,null,null,15,7]" 来表示一棵树，
可以直接把这个方法放到树操作的工具类里。之后调试创建树的时候就可以一键生成啦！！
/**
* description: strToTree
* // String str = "[3,9,20,null,null,15,7]";
* @AuThor Wang Hai Xin
* @date 2023/3/22 17:10
*
* @Param str
* @Return cn.wanghaixin.solution.utils.TreeNode
*/
public static TreeNode strToTree(String str) {
Integer[] integers = stringToArray(str);
TreeNode treeNode = constructTree(integers);
return treeNode;
}
/**
* description: constructTree将数组转化为二叉树
* @author Wang Hai Xin
* @date 2023/3/22 17:11
*
* @param array
* @return cn.wanghaixin.solution.utils.TreeNode
*/
public static TreeNode constructTree(Integer[] array) {
if (array == null || array.length == 0 || array[0] == null) {
return null;
}
int index = 0;
int length = array.length;
TreeNode root = new TreeNode(array[0]);
Deque<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.offer(root);
TreeNode currNode;
while (index < length) {
index++;
if (index >= length) {
return root;
}
currNode = nodeQueue.poll();
Integer leftChild = array[index];
if (leftChild != null) {
currNode.left = new TreeNode(leftChild);
nodeQueue.offer(currNode.left);
}
index++;
if (index >= length) {
return root;
}
Integer rightChild = array[index];
if (rightChild != null) {
currNode.right = new TreeNode(rightChild);
nodeQueue.offer(currNode.right);
}
}
return root;
}
涉及到的将str转化为array
stringToArray
/**
* description: stringToArray 将数字类型的字符数组转化为 int类型的数组
*
* @param data
* @return java.lang.Integer[]
* @author Wang Hai Xin
* @date 2023/1/12 18:28
*/
public static Integer[] stringToArray(String data) {
data = data.substring(1, data.length() - 1).trim();
String[] split = data.split(",");
int len = split.length;
Integer[] res = new Integer[len];
for (int i = 0; i < len; i++) {
if (split[i].equals("null")) {
res[i] = null;
} else {
res[i] = Integer.parseInt(split[i].trim());
}
}
return res;
}
4 如何打印一棵树
在这里，我的总体思路是，用一个二维的字符串数组来储存每个位置应该打印什么样的输出。
首先，先确定树的形状。为了美观，我设定在最后一行的每个数字之间的间隔为3个空格，而在之上的每一层的间隔，有兴趣的同学可以自己推算一下，总之，越往上，间隔是越大的，而且是一个简单的线性增加的关系。
为了绘制出这样的形状，首先，我们需要获得树的层数（用一个简单的递归即可得到），根据树的层数，确定我们的二维数组的大小，即高度和宽度。之后，用先序遍历的方式，遍历树的每个节点，并进行相对应的写入操作。
更详细的解释可以看代码中的注释，当然，也可以根据下面TreeNode.java中的demo直接在自己的代码中调用这个方法来检查自己的树。
话不多说，直接贴上所用的代码：
/*
树的结构示例：
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），才可以正常使用。
public class P236_LowestCommonAncestorOfABinaryTree{
public static void main(String[] args) {
String s = "[3,5,1,6,2,0,8,null,null,7,4]";
TreeNode treeNode = TreeNode.strToTree(s);
TreeNode.show(treeNode);
Solution();
}
输出：
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
进程已结束,退出代码0
可以看到，之后我们只用两行代码，便创建出了一棵我们需要的树，并且按照树的格式将一棵完整的树打印了出来。无论是创建还是打印出来分析调试，都是非常棒的工具。
4 不足之处
由于本方法的思路是基于字符串的数组的，所以并不可能完美适配所有情况，比如当树的高度很高以后，可能看起来会很奇怪。
还有一个问题就是，虽然已经做了自适应处理，但是，如果出现超过5位的数字（比如123123），其所在的行可能会有一点向右的偏移，若偏的不多，是不影响观察的，但若偏的多了就。。。。不过这里已经做了处理，所以出现三位或者四位数的时候是没有问题的。
不过，在日常的应用中，应该是完全够用的，希望这段代码能为大家带来便利。
5 完整代码
TreeNode的工具类：
直接将下面的代码引入自己的项目，调用就可以快速创建一个TreeNode和观察一个TreeNode的结构
package cn.wanghaixin.solution.utils;
import com.alibaba.fastjson.JSON;
import java.util.ArrayList;
import java.util.List;
/**
* @program: health_band_webserver
* @description: 操作数组的工具类
* @author: Wang Hai Xin
* @create: 2022-11-01 18:04
**/
public class ArrayUtil {
/**
* description: 打印list
* @author Wang Hai Xin
* @date 2023/3/17 13:49
*
* @param data
* @return java.lang.String
*/
public static String arrayListToString(List data) {
String s = JSON.toJSON(data).toString();
return s;
}
public static String arrayToString(int[] data) {
int len = data.length;
StringBuilder res = new StringBuilder();
res.append("[");
for (int i = 0; i < len; i++) {
if (i == len-1) {
res.append(data[i]);
}else{
res.append(data[i]+",");
}
}
res.append("]");
return res.toString();
}
/**
* description: StrToCharacterArray
* 二维数组字符串转化为二维Character数组
* [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
* @author Wang Hai Xin
* @date 2023/3/14 15:26
*
* @param str
* @return java.lang.Character[][]
*/
public static Character[][] StrToCharacterArray(String str) {
//字符串转换成二维数组
Character[][] characters = JSON.parseObject(str, Character[][].class);
return characters;
}
/**
* description: IntegerToStrArray
* Integer[][] toStr= new Integer[][]{{1,2,3},{4,5,6}};
*二维integer数组转化为字符串
* @param array
* @return java.lang.String
* @author Wang Hai Xin
* @date 2023/3/14 15:24
*/
public static String IntegerToStrArray(Integer[][] array) {
String s = JSON.toJSON(array).toString();
return s;
}
/**
* description: StrToIntArrayAll
* <p>二维Integer数组字符串转化为Integer数组
* String s = "[[22,23,23],[1,10,20]]";
*
* @param str
* @return java.lang.Integer[][]
* @author Wang Hai Xin
* @date 2023/3/14 15:22
*/
public static Integer[][] StrToIntegerArray(String str) {
//字符串转换成二维数组
Integer[][] parse = JSON.parseObject(str, Integer[][].class);
return parse;
}
/**
* description: StrToArrayList 数组字符串转list
* @author Wang Hai Xin
* @date 2023/3/22 17:01
*
* @param str [1,null,2,3]
* @return java.util.List<java.lang.Integer>
*/
public static List<Integer> StrToArrayList(String str) {
str = str.substring(1, str.length() - 1).trim();
String[] strs = str.split(",");
List<Integer> arr = new ArrayList(strs.length);
if (str.equals("")) {
return null;
}
for (int i = 0; i < strs.length; i++) {
if (strs[i].equals("null")) {
arr.add(null);
} else {
arr.add(Integer.parseInt(strs[i]));
}
}
return arr;
}
/**
* description: StrToIntArray 将数组字符串转化为数组
* int []arr = {3, 9, 20, Integer.MAX_VALUE, Integer.MAX_VALUE, 15, 7};
* 将字符数组转化为数字数组
* @author Wang Hai Xin
* @date 2023/3/16 14:35
*
* @param str
* @return int[]
*/
public static int[] StrToIntArray(String str) {
str = str.substring(1, str.length() - 1).trim();
String[] strs = str.split(",");
int[] arr = new int[strs.length];
if (str.equals("")) {
return null;
}
for (int i = 0; i < arr.length; i++) {
if (strs[i].equals("null")) {
arr[i] = Integer.MAX_VALUE;
} else {
arr[i] = Integer.parseInt(strs[i]);
}
}
return arr;
}
/**
* description: arraysAvgFileZero 求数组平均值 排除零
*
* @param data
* @return java.lang.Integer
* @author Wang Hai Xin
* @date 2023/1/12 18:30
*/
public static Integer arraysAvgFileZero(Integer[] data) {
int len = data.length;
if (data == null && 0 == len) {
return 0;
}
Integer sum = 0;
Integer num = 0;
for (int i = 0; i < len; i++) {
if (data[i] != 0) {
sum += data[i];
num++;
}
}
if (num != 0) {
return sum / num;
} else {
return sum;
}
}
/**
* description: ArraysAvg 求数组平均值
*
* @param data
* @return java.lang.Integer
* @author Wang Hai Xin
* @date 2022/11/1 18:12
*/
public static Integer arraysAvg(Integer[] data) {
int len = data.length;
if (data == null && 0 == len) {
return 0;
}
Integer sum = 0;
for (int i = 0; i < len; i++) {
sum += data[i];
}
return sum / len;
}
/**
* description: stringToArray 将数字类型的字符数组转化为 int类型的数组
*
* @param data
* @return java.lang.Integer[]
* @author Wang Hai Xin
* @date 2023/1/12 18:28
*/
public static Integer[] stringToArray(String data) {
data = data.substring(1, data.length() - 1).trim();
String[] split = data.split(",");
int len = split.length;
Integer[] res = new Integer[len];
for (int i = 0; i < len; i++) {
if (split[i].equals("null")) {
res[i] = null;
} else {
res[i] = Integer.parseInt(split[i].trim());
}
}
return res;
}
}
6 AC
我也通过工具类快速AC了这道题目：
解答成功:
执行耗时:6 ms,击败了99.98% 的Java用户
内存消耗:42.9 MB,击败了35.02% 的Java用户
关于算法题的题解 可以看我的算法系列文章，希望对大家有所帮助。
发表于 2023-3-29 09:44
发表于 2023-3-29 10:42
|
发表于 2023-3-30 10:02
