前言
之前在力扣刷二叉树类型的题目时，经常会遇到bug，代码的结果和自己的预期不符，此时想到本地调试，却要先构造一个二叉树作为输入。之前一直用的笨方法，就是一个个new节点，然后把指针连起来。如果运气不好，这棵树运行成功了，又卡在另一棵树上，又要重新构造一棵树，很麻烦，导致我想放弃调试了。在网上也没有找到相关的转换代码，正好前几天做到 二叉树的序列化与反序列化 这道题，发现刚好和这个需求匹配。
构造二叉树工具类
废话不多说，直接上代码，可以拿去直接用。
/**
* 二叉树调试工具类
* 根据层次遍历的二叉树字符串形式构造二叉树
*/
class TreeUtils {
// 分隔符
String SEP = ",";
// 空值
String NULL = "null";
/* 将字符串反序列化为二叉树结构 */
TreeNode buildTree(String data) {
if (data.isEmpty()) return null;
// 去除首位"[", "]"
data = data.substring(1,data.length()-1);
// 在data后加若干个空值
for(int i = 0; i < 100; i++) data += SEP + NULL;
String[] nodes = data.split(SEP);
// 第一个元素就是 root 的值
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
// 队列 q 记录父节点，将 root 加入队列
Queue
q.offer(root);
for (int i = 1; i < nodes.length; ) {
// 队列中存的都是父节点
TreeNode parent = q.poll();
if(parent == null) break;
// 父节点对应的左侧子节点的值
String left = nodes[i++];
if (!left.equals(NULL)) {
parent.left = new TreeNode(Integer.parseInt(left));
q.offer(parent.left);
} else {
parent.left = null;
}
// 父节点对应的右侧子节点的值
String right = nodes[i++];
if (!right.equals(NULL)) {
parent.right = new TreeNode(Integer.parseInt(right));
q.offer(parent.right);
} else {
parent.right = null;
}
}
return root;
}
}
使用方法
比如，我今天做 652. 寻找重复的子树 这道题的时候，遇到bug，想在本地调试自己的代码，因此我需要用上述工具类构造出我没过的那个二叉树，再一步步调试我的代码。
比如，想构造下图所示二叉树
本地调试代码如下
Main.java
public class Main {
public static void main(String[] args) {
// 自己的解法
Solution s = new Solution();
// 构造二叉树工具类
TreeUtils treeUtils = new TreeUtils();
// 将力扣的二叉树输入复制过来作为构造二叉树的参数
TreeNode root = treeUtils.buildTree("[1,2,3,4,null,2,4,null,null,4]");
// 将构造好的二叉树作为解法参数传入，调试自己的代码
List
// 查看输出
System.out.println(duplicateSubtrees);
return;
}
}
Solution.java
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* 二叉树调试工具类
* 根据层次遍历的二叉树字符串形式构造二叉树
*/
class TreeUtils {
// 分隔符
String SEP = ",";
// 空值
String NULL = "null";
/* 将字符串反序列化为二叉树结构 */
TreeNode buildTree(String data) {
if (data.isEmpty()) return null;
// 去除首位"[", "]"
data = data.substring(1,data.length()-1);
// 在data后加若干个空值
for(int i = 0; i < 100; i++) data += SEP + NULL;
String[] nodes = data.split(SEP);
// 第一个元素就是 root 的值
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
// 队列 q 记录父节点，将 root 加入队列
Queue
q.offer(root);
for (int i = 1; i < nodes.length; ) {
// 队列中存的都是父节点
TreeNode parent = q.poll();
if(parent == null) break;
// 父节点对应的左侧子节点的值
String left = nodes[i++];
if (!left.equals(NULL)) {
parent.left = new TreeNode(Integer.parseInt(left));
q.offer(parent.left);
} else {
parent.left = null;
}
// 父节点对应的右侧子节点的值
String right = nodes[i++];
if (!right.equals(NULL)) {
parent.right = new TreeNode(Integer.parseInt(right));
q.offer(parent.right);
} else {
parent.right = null;
}
}
return root;
}
}
// 652. 寻找重复的子树
class Solution {
List
HashMap
public List
traverse(root);
return res;
}
String traverse(TreeNode root){
if(root == null) return "#";
String left = traverse(root.left);
String right = traverse(root.right);
String rootStr = left + "," + right + "," + root.val;
if(map.getOrDefault(rootStr, 0) == 1){
res.add(root);
}
map.put(rootStr, map.getOrDefault(rootStr, 0) + 1);
return rootStr;
}
}
代码思路
主体代码参考东哥的东哥带你刷二叉树（序列化篇） 主要是借鉴用层次遍历解决二叉树的序列化与反序列化的思路，但有一点改变。
力扣给出的二叉树输入形式是省略了末尾一些null值的，类似完全二叉树而用层次遍历反序列化二叉树需要给出所有的null值，类似满二叉树
举个例子 在 652. 寻找重复的子树 题目中的示例，力扣给出的二叉树输入形式如下图所示
而层次遍历反序列化二叉树的输入形式应该如下图所示
输入: root = [1,2,3,4,null,2,4,null,null,4,null,null,null]
解决办法也很容易，就是在力扣的输入后面加若干个null值
// 在data后加若干个空值
for(int i = 0; i < 100; i++) data += SEP + NULL;
工具类中已经解决，直接复制力扣的输入即可。
参考资料
东哥带你刷二叉树（序列化篇）