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

Donne 發(fā)布于2019-08-22 18:47 / 2122人閱讀

摘要：題目描述請實(shí)現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹分析可以使用前序遍歷的方法來得到二叉樹的序列，然后再每個節(jié)點(diǎn)之間得使用一個來隔開，這樣可以避免節(jié)點(diǎn)值之間的歧義對于空節(jié)點(diǎn)也需要存儲下來，所以使用來存儲。反序列化就解析序列化字符串即可。

題目描述

請實(shí)現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹

分析

可以使用前序遍歷的方法來得到二叉樹的序列，然后再每個節(jié)點(diǎn)之間得使用一個" ! "來隔開，這樣可以避免節(jié)點(diǎn)值之間的歧義；對于空節(jié)點(diǎn)也需要存儲下來，所以使用" # "來存儲。

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

代碼實(shí)現(xiàn)

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云服務(wù)器云服務(wù)器序列化和反序列化二叉樹算法最優(yōu)二叉樹算法圖最大功序列算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/96209.html

相關(guān)文章

【刷算法】判斷二叉搜索樹的后序遍歷序列的遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)

摘要：題目描述輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。那么對于二叉搜索樹的后序遍歷的序列來說，最后一個元素即是它的根節(jié)點(diǎn)，序列的前某部分元素全部小于最后一個元素，序列的后某部分元素全大于最后一個元素。題目描述輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。分析所謂二叉搜索...

Anshiii 2019-08-22 18:20 評論0 收藏0
【刷算法】重建二叉樹

題目描述輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{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是根節(jié)點(diǎn)，然...

Blackjun 2019-08-22 18:50 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時(shí)間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點(diǎn)個數(shù)。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點(diǎn)組成一個...

RaoMeng 2019-08-19 11:08 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時(shí)間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點(diǎn)個數(shù)。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點(diǎn)組成一個...

PiscesYE 2019-07-30 17:45 評論0 收藏0
二叉樹的一些常見的操作

摘要：節(jié)點(diǎn)類二叉樹類實(shí)現(xiàn)了二叉樹插入刪除查找前序遍歷中序遍歷后序遍歷層序遍歷二叉樹序列化和反序列化二叉樹的常見操作增加刪除查找先序中序后序?qū)有虮闅v序列化二叉樹先序?qū)有蛐蛄谢头葱蛄谢刃蚍葱蛄谢瘜有蛐蛄谢瘜有蚍葱蛄谢瘮?shù)據(jù)測試建立一棵二叉樹參考資料節(jié)點(diǎn)類 public class Node { public Node left; public Node...

Aldous 2019-08-14 14:42 評論0 收藏0