算法-二叉树-序列化&反序列化

2022-4-11 diaba 笔试题 

package com.jiucaiyuan.net.algrithm.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树的序列化与反序列化
 *
 * @Author jiucaiyuan  2022/4/11 22:57
 * @mail services@jiucaiyuan.net
 */
public class SerializeAndDeserializeTree {
    /**
     * 先序遍历-序列化
     * #表示null _表示值结束
     */
    public static String serialByPre(Node root) {
        if (root == null) {
            return "#_";
        }
        String res = root.value + "_";
        res += serialByPre(root.left);
        res += serialByPre(root.right);
        return res;
    }
    /**
     * 先序遍历-反序列化
     * #表示null _表示值结束
     */
    public static Node deSerialByPre(String preStr) {
        String[] values = preStr.split("_");
        Queue<String> queue = new LinkedList<>();
        for(String value:values){
            queue.add(value);
        }
        return deSerialPreOrder(queue);
    }

    private static Node<Integer> deSerialPreOrder(Queue<String> queue) {
        String value = queue.poll();
        if (value.equals("#")){
            return null;
        }
        Node<Integer> node = new Node(Integer.valueOf(value));
        node.left = deSerialPreOrder(queue);
        node.right = deSerialPreOrder(queue);
        return node;
    }

    public static void main (String[] args){
        String preOrder = "1_#_1_1_#_#_#_";
        Node head = deSerialByPre(preOrder);
        PrintBinaryTree.printTree(head);
        System.out.println(serialByPre(head));
        
        String preOrder2 = "1_1_#_1_#_#_#_";
        Node head2 = deSerialByPre(preOrder2);
        PrintBinaryTree.printTree(head2);
        System.out.println(serialByPre(head2));
    }

}

« 算法-二叉树-折纸问题 | 算法-二叉树-最低公共祖先»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022