力扣二叉树调试工具类——根据力扣数组输入形式的二叉树构造真正的二叉树

/**
 * 二叉树调试工具类
 * 根据层次遍历的二叉树字符串形式构造二叉树
 */
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<TreeNode> q = new LinkedList<>();
        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;
    }
}

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<TreeNode> duplicateSubtrees = s.findDuplicateSubtrees(root);
        // 查看输出
        System.out.println(duplicateSubtrees);
        return;
    }
}

// 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<TreeNode> q = new LinkedList<>();
        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<TreeNode> res = new LinkedList<>();
    HashMap<String, Integer> map = new HashMap<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        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;
    }
}

输入: root = [1,2,3,4,null,2,4,null,null,4,null,null,null]

// 在data后加若干个空值
for(int i = 0; i < 100; i++) data += SEP + NULL;