专栏首页全部文章Day61:序列化二叉树

Day61:序列化二叉树

剑指Offer_编程题——序列化二叉树

题目描述:

请实现两个函数,分别用来序列化和反序列化二叉树。 二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#),以 ! 表示一个结点值的结束(value!)。 二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。 例如,我们可以把一个只有根节点为1的二叉树序列化为"1,",然后通过自己的函数来解析回这个二叉树

具体要求:

时间限制: C/C++ 1秒,其他语言2秒 空间限制: C/C++32M,其他语言64M

具体实现:

思路一:   序列化就是按照前序遍历的顺序将其输出为一个字符串,节点为空则用#代替,反序列化就是讲一个字符串恢复成为一个树。接下来我们分别用java将其实现:

public class Solution{
	private String remainString;
	String Serialize(TreeNode root){
		if(root == null)
			return "#";
		return root.val+" "+Serialize(root.left)+" "+Serialize(root.right);
	}
	TreeNode Deserialize(String str){
		remainString = str;
		return Deserialize();
	}
	TreeNode Deserialize(){
		if(remainString == null)
			return null;
		int index = remainString.indexOf(" ");
		String node = (index == -1)?remainString:remainString.substring(0,index);
		remainString = (index == -1)?"":remainString.substring(index+1);
		if(node.equals("#")){
			return null;
		}
		int val = Integer.valueOf(node);
		TreeNode t = new TreeNode(val);
		t.left = Deserialize();
		t.right = Deserialize();
		return t;
	}
}

代码效果图如图所示:

  正如前面说的那样,如果在牛客网中,我们可以直接通过,但是如果是本地的编译器,则还需要定义其结点,具体结点的实现定义用java实现如下:

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

  我们在代码中发现:字符串的indexof方法,没有的话则返回-1;字符串的substring方法,包含头不包含尾,如果只输入一个参数的话,则由当前位置到最后;判断字符串内容是否相同要用equals方法,而不是用==以及Integer.valueOf将字符串转为int类型。 思路二: 1、利用前序遍历序列化二叉树,然后从记录的字符串中反序列化二叉树。 2、遇到空节点需要用特殊字符加以标记。如“#”   接下来我们用java将其实现:

public class Solution{
	public int index = -1;
	String Serialize(TreeNode root) {
		StringBuilder s = new StringBuilder();
		if(root == null){
			s.append("#,");
			return s.toString();
		}
		s.append(root.val+",");
		s.append(Serialize(root.left));
		s.append(Serialize(root.right));
		return s.toString();
	}
	TreeNode Deserialize(String str){
		index++;
		String[] DLRseq = str.split(",");
		TreeNode leave = null;
		if(!DLRseq[index].equals("#")){
			leave = new TreeNode(Integer.valueOf(DLRseq[index]));
			leave.left = Deserialize(str);
			leave.right = Deserialize(str);
		}
		return leave;
	}
}

代码效果图如图所示:

思路三:   在思路二的基础上进行了改变,将前序遍历换为层次遍历,具体过程如下: 1、层序遍历二叉树,序列化二叉树 2、空节点需要使用特殊字符记录。将二叉树序列化成为一颗完全二叉树,然后反序列化二叉树。

import java.util.*;
public class Solution{
	String Serialize(TreeNode root){
		if(root == null)
			return null;
		StringBuffer sb = new StringBuffer();
		ArrayList<TreeNode> list = new ArrayList<>();
		int count = (1 << treeDepth(root)) - 1;
		list.add(root);
		count--;
		TreeNode tmpNode = null;
		while(list.size() > 0 && count >= 0){
			tmpNode = list.remove(0);
			if(tmpNode != null){
				sb.append(tmpNode.val + ",");
				list.add(tmpNode.left);
				list.add(tmpNode.right);
			}else{
				sb.append("#,");
				list.add(null);
				list.add(null);
			}
			count--;
		}
		return sb.toString();
	}
	TreeNode Deserialize(String str){
		if(str == null || str.length() == 0)
			return null;
		return Deserialize(str.split(","), 0);
	}
	TreeNode Deserialize(String[] strings, int index){
		TreeNode newNode = null;
		if(index < strings.length){
			if(!strings[index].equals("#")){
				newNode = new TreeNode(Integer.parseInt(strings[index]));
				newNode.left = Deserialize(strings, 2 * index + 1);
				newNode.right = Deserialize(strings, 2 * index + 2);
			}
		}
		return newNode;
	}
	int treeDepth(TreeNode root){
		int depth = 0;
		if(root == null)
			return depth;
		else{
			int lDepth = treeDepth(root.left)+1;
			int rDepth = treeDepth(root.right) + 1;
			return lDepth > rDepth?lDepth:rDepth;
		}
	}
}

代码效果图如图所示:

思路四:   二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字 符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层次遍历的二叉树遍历方式来进行序列化。原理都是一样的(即遍历顺序不同而已,对每个结点的处理都是一样的),序列化的结果是一个字符串,序列化时通过某种符号表示空节点(#)。这里以先序遍历的方式对二叉树进行序列化。先序序列化二叉树:定义一个res数组保存序列过程中的结果:按照先序遍历方式遍历二叉树,若结点非空则把 “结点值” append到res中;若结点空则把 “#” append到res中;最后用用res数组生成字符串就是序列化结果。   二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。先序序列化结果重构二叉树:分割二叉树的序列化字符串,遍历nodes数组建立二叉树,如果当前遍历元素非 # 则作为一个结点插入树中作为上一结点的左儿子,当前遍历元素为 # 则表示此子树已结束,遍历下一元素作为上一结点的右儿子。接下来我们分别用Java和python两种编程语言将其实现。 1、首先我们用java将其实现:

public class Solution{
	public String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            return "";
        }
        preOrder(root, sb);
        return sb.toString();
    }

    public void preOrder(TreeNode root, StringBuilder sb) {
        if (root != null) {
            sb.append(root.val + "!");
            preOrder(root.left, sb);
            preOrder(root.right, sb);
        } else {
            sb.append("#!");
        }
    }

    public TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        String[] nodes = str.split("!");
        return buildTree(nodes);
    }

    int index = -1;

    public TreeNode buildTree(String[] nodes) {
        index++;
        TreeNode node = null;
        if (index == nodes.length) {
            return null;
        }
        if (!"#".equals(nodes[index])) {
            node = new TreeNode(Integer.valueOf(nodes[index]));
            node.left = buildTree(nodes);
            node.right = buildTree(nodes);
        }
        return node;
    }
  }

代码效果图如图所示:

2、接下来我们用python将其实现

class Solution:
	def Serialize(self, root):
		vallist = []
		def preOrder(root):
			if not root:
				vallist.append('#')
			else:
				vallist.append(str(root.val))
				preOrder(root.left)
				preOrder(root.right)
		preOrder(root)
		return ' '.join(vallist)
	def Deserialize(self, s):
		vallist = iter(s.split())
		def dePre():
			val = next(vallist)
			if val == "#":
				return None
			node = TreeNode(int(val))
			node.left = dePre()
			node.right = dePre()
			return node
		return dePre()

代码效果图如图所示:

  但是在本地编译器中我们还需要定义链表结构才能正常运行,具体用python定义树结构实现如下:

class TreeNode:
	def __init__(self, pNode):
		self.val = x
		self.left = None
		self.right = None

  在上述的代码中我们其实使用了一个迭代器,通过next不断调用迭代器里的元素。这里当然也可以利用一个队列,不断返回队列中最左边的元素,并删除。 思路五:   在题目中给出了序列化的定义:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串。需要注意的是,序列化二叉树的过程中,如果遇到空节点,需要以某种符号(这里用#)表示。具体入下图所示:

  从上图二叉树的序列化可知:序列化二叉树时,需要将空节点也存入字符串中。序列化可以基于先序/中序/后序/按层等遍历方式进行,这里采用先序遍历的方式实现,字符串之间用 “,”隔开。反序列化二叉树:根据某种遍历顺序得到的序列化字符串,重构二叉树。具体思路是按前序遍历“根左右”的顺序,根节点位于其左右子节点的前面,即非空(#)的第一个节点是某子树的根节点,左右子节点在该根节点后,以空节点#为分隔符。具体用python实现:

class Solution:
	def Serialize(self, root):
		if not root:
			return '#'
		return str(root.val)+','+self.Serialize(root.left)+','+self.Serialize(root.right)
	def Deserialize(self, s):
		list = s.split(',')
		return self.deserializeTree(list)
	def deserializeTree(self, list):
		if len(list) <= 0:
			return None
		val = list.pop(0)
		root = None
		if val != '#':
			root = TreeNode(int(val))
			root.left = self.deserializeTree(list)
			root.right = self.deserializeTree(list)
		return root

代码效果图如图所示:

总结

  本题主要通过序列化二叉树来考察二叉树的遍历以及队列的使用。本题给出了五种解题思路,从前序遍历入手到递归以及分别用java和python将其实现。并且介绍了在字符比较的时候,用到的是equals()函数,而不是==。因此,我们在做题的时候,应该多次尝试各种方法,扩展自己的思维,写出优质的代码。总之,我们要继续加油,争取早日找到工作,Good Luck!!!

参考文献

[1] IDEA_TEYU_1112 [2] ouyangyanlan [3] 超人不会飞、 [4] 乖乖的函数 [5] goddaniel

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day18:二叉树的镜像

      由于本题的本质就是考察二叉树,因此还是得用到递归的方法。其实本题就是将二叉树的左右子树进行交换即可。因此我们可以从根节点开始遍历,如果遍历的节点有子结点,就...

    stefan666
  • Day64:滑动窗口的最大值

    背景知识介绍:   在做题之前,我们首先给大家介绍队列中的双端队列。 我们知道普通队列是限制级的一端进,另一端出的FIFO形式,栈是一端进出的LIFO形式,而...

    stefan666
  • Day62:二叉搜索树的第k个结点

    背景知识介绍:   在前面的文章中我们详细的介绍了二叉搜索树的相关概念,接下来我们介绍二叉搜索树的具体应用。二叉排序树又称二叉查找树(二叉搜索树),它或是一棵...

    stefan666
  • 检查一个二叉树是否是平衡二叉树leecode111

    用户7962184
  • 如何在Kerberos环境下的CDH集群部署Spark1.6 Thrift及spark-sql客户端

    Fayson
  • 51Nod 1016 水仙花数 V2(组合数学,枚举打表法)

    1016 水仙花数 V2 基准时间限制:1 秒 空间限制:131072 KB 分值: 160         难度:6级算法题 水仙花数是指一个 n 位数 ...

    Angel_Kitty
  • 腾讯WeTest助力游戏不再负重安全压力

    根据CNNIC第42次《中国互联网络发展状况》调查显示,截至2018年5月,我国市场上监测到的游戏类移动应用程序数量为152万,避开版号审批等问题不谈,总量依然...

    WeTest质量开放平台团队
  • 改造尚未完成,互联网家装仍将洗牌

    孟永辉
  • 使用pscp从windows电脑拷贝数据到linux遇到的ssh_init错误

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Jerry Wang
  • 《梦幻模拟战》漏洞挖掘全过程

    原文链接:https://wetest.qq.com/lab/view/429.html

    WeTest质量开放平台团队

扫码关注云+社区

领取腾讯云代金券