【剑指Offer】061——序列化二叉树 （树）

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

解题思路

1. 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在每次二叉树的结点不为空时，在转化val所得的字符之后添加一个’,’作为分割; 对于空节点则以 ‘#,’ 代替。
2. 对于反序列化：将字符串按照“，”进行分割，插入到队列中，然后依次从队列中取出字符建立节点，递归创建一个二叉树。

参考代码

Java

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    // 序列化
    String Serialize(TreeNode root) {
        if(root == null){
            return "#,";
        }
        // 前序遍历
        StringBuffer res = new StringBuffer(root.val + ","); // 可变字符串
        res.append(Serialize(root.left)); //
        res.append(Serialize(root.right));//
        return res.toString();
    }
    // 反序列化
    TreeNode Deserialize(String str) {
        String [] res = str.split(","); // 将数据切割
        Queue<String> queue = new LinkedList<String>(); // 序列
        for(int i = 0; i < res.length; i++){
            queue.offer(res[i]); // 链表添加内容
        }
        return pre(queue); // 通过递归生成
    }
    TreeNode pre(Queue<String> queue){
        String val = queue.poll(); // 弹出值（弹出的不是结点）
        if(val.equals("#"))
            return null;
        TreeNode node = new TreeNode(Integer.parseInt(val)); // 创建结点
        // 按照前序的方式返回去
        node.left = pre(queue);
        node.right = pre(queue);
        return node;
    }
}

Python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return "#"
        return str(root.val) + "," + self.Serialize(root.left)+ "," + self.Serialize(root.right)
    def Deserialize(self, s): 
        # write code here
        return self.pre(s.split(","))
    def pre(self, res):
        val = res.pop(0)
        if val == "#":
            return None
        node = TreeNode(int(val))
        node.left = self.pre(res)
        node.right = self.pre(res)
        return node

个人订阅号