【刷算法】序列化和反序列化二叉树

Donne 发布于2019-08-22 18:47 / 1980人阅读

摘要：题目描述请实现两个函数，分别用来序列化和反序列化二叉树分析可以使用前序遍历的方法来得到二叉树的序列，然后再每个节点之间得使用一个来隔开，这样可以避免节点值之间的歧义对于空节点也需要存储下来，所以使用来存储。反序列化就解析序列化字符串即可。

题目描述

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

分析

可以使用前序遍历的方法来得到二叉树的序列，然后再每个节点之间得使用一个" ! "来隔开，这样可以避免节点值之间的歧义；对于空节点也需要存储下来，所以使用" # "来存储。

反序列化就解析序列化字符串即可。

代码实现

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function Serialize(r)
{
    if(r === null)
        return "#!";
    var res = "";
    var s = [];
    s.push(r);
    
    while(s.length !== 0){
        var cur = s.pop();
        res += (cur === null) ? "#" : cur.val;
        res += "!";
        if(cur !== null) {
            s.push(cur.right);
            s.push(cur.left);
        }
    }
    return res;
}
function Deserialize(s)
{
    if(s === "")
        return null;
    var arr = s.split("!");
    
    return step(arr);
}

function step(arr) {
    var cur = arr.shift();
    if(cur === "#")
        return null;
    var node = new TreeNode(cur);
    node.left = step(arr);
    node.right = step(arr);
    
    return node;
}

云服务器 GPU云服务器序列化和反序列化二叉树算法最优二叉树算法图最大功序列算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96209.html

【刷算法】判断二叉搜索树的后序遍历序列的递归实现和非递归实现

摘要：题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。那么对于二叉搜索树的后序遍历的序列来说，最后一个元素即是它的根节点，序列的前某部分元素全部小于最后一个元素，序列的后某部分元素全大于最后一个元素。题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。分析所谓二叉搜索...

Anshiii 2019-08-22 18:20 评论0 收藏0
【刷算法】重建二叉树

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。分析前序遍历是中左右的顺序，中序遍历是左中右的顺序，那么对于{1,2,4,7,3,5,6,8}和{4,7,2,1,5,3,8,6}来说，1是根节点，然...

Blackjun 2019-08-22 18:50 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

RaoMeng 2019-08-19 11:08 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

PiscesYE 2019-07-30 17:45 评论0 收藏0
二叉树的一些常见的操作

摘要：节点类二叉树类实现了二叉树插入删除查找前序遍历中序遍历后序遍历层序遍历二叉树序列化和反序列化二叉树的常见操作增加删除查找先序中序后序层序遍历序列化二叉树先序层序序列化和反序列化先序反序列化层序序列化层序反序列化数据测试建立一棵二叉树参考资料节点类 public class Node { public Node left; public Node...

Aldous 2019-08-14 14:42 评论0 收藏0