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

Donne 發布于2019-08-22 18:47 / 2111人閱讀

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

題目描述

請實現兩個函數，分別用來序列化和反序列化二叉樹

分析

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

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

代碼實現

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云服務器序列化和反序列化二叉樹算法最優二叉樹算法圖最大功序列算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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