二叉树的序列化

[编程题]二叉树的序列化

热度指数：1886 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

二叉树被记录为文件的过程叫作二叉树的序列化，通过文件内容重建原来二叉树的过程叫作二叉树的反序列化，给定一颗二叉树，请将该二叉树先序序列化和层序序列化。

假设序列化的结果字符串为 str，初始时 str = ""，遍历二叉树时，遇到 null 节点，则在 str 的末尾加上 "#!"，否则加上"当前的节点值!"。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

输出两行分别表示该二叉树的先序序列化和层序序列化

示例1

输入

2 1
1 2 0
2 0 0

输出

1!2!#!#!#!
1!2!#!#!#!

备注:

算法知识视频讲解

Java

Ruoji55555

内存超限:您的程序使用了超过限制的内存

case通过率为0.00%

。。懵了

import java.io.*;
import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        TreeNode root = createSearchTree(br);
        br.close();

        fun(root);
    }

    private static void fun(TreeNode root) {
      
        System.out.println(preOrder(root));
       
        System.out.println(levelOrder(root));
    }
    
    private static String preOrder(TreeNode root){
        if(root == null) return "#!";
        String res = root.val+"!";
        res+= preOrder(root.left);
        res+=preOrder(root.right);
        return res;
    }
    private static String levelOrder(TreeNode root){
        if(root == null) return "#!";
        Deque<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        sb.append(root.val+"!");
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur.left != null){
                queue.offer(cur.left);
                sb.append(cur.left.val+"!");
            }else{
                sb.append("#!");
            }
            if(cur.right != null){
                queue.offer(root.right);
                sb.append(cur.right.val+"!");
            }else{
                sb.append("#!");
            }
        }
        return sb.toString();
    }


    // 递归创建二叉树
    private static TreeNode createSearchTree(BufferedReader br) {
        try {
            String[] rawInput = br.readLine().trim().split(" ");
            int value = Integer.parseInt(rawInput[0]);
            int left = Integer.parseInt(rawInput[1]);
            int right = Integer.parseInt(rawInput[2]);

            TreeNode treeNode = new TreeNode(value);
            if (0 != left) {
                treeNode.left = createSearchTree(br);
            }
            if (0 != right) {
                treeNode.right = createSearchTree(br);
            }
            return treeNode;
        } catch (IOException e) {
            return null;
        }
    }
}

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int value) {
        this.val = value;
        this.left = null;
        this.right = null;
    }
}

编辑于 2020-11-04 21:43:00 回复(1)