請實作兩個函式，分別用來序列化和反序列化二叉樹
二叉樹的序列化是指：把一棵二叉樹按照某種遍歷方式的結果以某種格式保存為字串，從而使得記憶體中建立起來的二叉樹可以持久保存，序列化可以基于先序、中序、后序、層序的二叉樹遍歷方式來進行修改，序列化的結果是一個字串，序列化時通過 某種符號表示空節點（#），以 ！ 表示一個結點值的結束（value!），
二叉樹的反序列化是指：根據某種遍歷順序得到的序列化字串結果str，重構二叉樹，
方法一：以陣列的方式存盤
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ const arr = []; function Serialize(pRoot) { // write code here if (pRoot === null) { arr.push('#'); } else { arr.push(pRoot.val); Serialize(pRoot.left); Serialize(pRoot.right); } } function Deserialize() { // write code here let node = null; if (arr.length < 1) { return null; } const root = arr.shift(); if (typeof root === 'number') { node = new TreeNode(root); node.left = Deserialize(); node.right = Deserialize(); } return node; }
方法二：以#表示null，！分隔，其實就是相當于在上述陣列方法中增加一步將其變為字串的形式進行存盤，
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; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24683.html
標籤：其他
上一篇：劍指Offer(第二版)面試題目分析與實作-高質量的代碼
下一篇：面試之Java虛擬機專題