網(wǎng)站規(guī)劃在網(wǎng)站建設中的作用是,H5平臺網(wǎng)站建設,9個成功的市場營銷案例,遼寧招投標信息網(wǎng)官網(wǎng)文章目錄摘要描述題解答案#xff08;核心思路#xff09;為什么普通二叉樹和 BST 不一樣#xff1f;BST 的關鍵點本題采用的策略題解代碼#xff08;Swift 可運行 Demo#xff09;題解代碼分析1. 為什么用前序遍歷#xff1f;2. serialize 的核心邏輯3. deserialize 的核…文章目錄摘要描述題解答案核心思路為什么普通二叉樹和 BST 不一樣BST 的關鍵點本題采用的策略題解代碼Swift 可運行 Demo題解代碼分析1. 為什么用前序遍歷2. serialize 的核心邏輯3. deserialize 的核心邏輯4. 為什么不需要回退 index示例測試及結(jié)果時間復雜度空間復雜度總結(jié)摘要「序列化和反序列化二叉搜索樹」這道題表面上是在考二叉樹其實真正的考點在于你有沒有真正理解 BSTBinary Search Tree的性質(zhì)。如果把它當成普通二叉樹去做確實可以用層序遍歷加上null占位來解決但那樣字符串會很長也完全沒有利用 BST 的特性。而題目特意強調(diào)了一句編碼的字符串應盡可能緊湊。這其實是在暗示BST 是可以只靠遍歷順序恢復出來的。這篇文章會從實際業(yè)務場景聊起解釋為什么 BST 可以被“無損壓縮”再一步步帶你用 Swift 寫出一套簡潔、高效、可運行的解法。描述題目要求我們設計一套算法用來把一棵二叉搜索樹序列化成字符串再從這個字符串中反序列化恢復成原來的 BST有幾個關鍵限制條件輸入保證一定是一棵 BST節(jié)點值范圍是合法整數(shù)節(jié)點數(shù)量最多 10?序列化字符串要盡量緊湊BST 有一個非常重要的性質(zhì)左子樹所有節(jié)點值 根節(jié)點右子樹所有節(jié)點值 根節(jié)點這條規(guī)則是我們能“少存信息、還能完整還原”的關鍵。題解答案核心思路為什么普通二叉樹和 BST 不一樣如果是普通二叉樹你只存前序遍歷是沒法還原結(jié)構(gòu)的比如1 2和1 / 2前序遍歷都是[1,2]結(jié)構(gòu)信息丟失了。但 BST 不一樣。BST 的關鍵點只要你知道遍歷順序比如前序BST 的大小關系規(guī)則那么不用存 null也能恢復結(jié)構(gòu)。本題采用的策略序列化使用前序遍歷root → left → right只記錄節(jié)點值用逗號拼成字符串反序列化根據(jù) BST 的區(qū)間規(guī)則遞歸構(gòu)建每個節(jié)點值都必須落在合法區(qū)間(min, max)內(nèi)一次遍歷即可還原整棵樹這樣做的好處是字符串非常緊湊時間和空間效率都很高思路清晰代碼不復雜題解代碼Swift 可運行 Demo下面是完整可運行的 Swift 示例包括TreeNode定義和測試代碼。importFoundationpublicclassTreeNode{publicvarval:Intpublicvarleft:TreeNode?publicvarright:TreeNode?publicinit(_val:Int){self.valvalself.leftnilself.rightnil}}classCodec{// MARK: - Serializefuncserialize(_root:TreeNode?)-String{varresult:[String][]funcpreorder(_node:TreeNode?){guardletnodenodeelse{return}result.append(String(node.val))preorder(node.left)preorder(node.right)}preorder(root)returnresult.joined(separator:,)}// MARK: - Deserializefuncdeserialize(_data:String)-TreeNode?{ifdata.isEmpty{returnnil}varvaluesdata.split(separator:,).map{Int($0)!}varindex0funcbuild(_min:Int,_max:Int)-TreeNode?{ifindexvalues.count{returnnil}letvalvalues[index]ifvalmin||valmax{returnnil}index1letnodeTreeNode(val)node.leftbuild(min,val)node.rightbuild(val,max)returnnode}returnbuild(Int.min,Int.max)}}題解代碼分析1. 為什么用前序遍歷前序遍歷的第一個節(jié)點一定是根節(jié)點這對構(gòu)建樹非常友好。BST 的前序遍歷有一個隱含規(guī)律一段連續(xù)小于 root 的值一定屬于左子樹后面大于 root 的值一定屬于右子樹結(jié)合區(qū)間限制我們就能精準判斷一個值“該不該被消費”。2. serialize 的核心邏輯funcpreorder(_node:TreeNode?){guardletnodenodeelse{return}result.append(String(node.val))preorder(node.left)preorder(node.right)}這里非常直接不存 null不加多余符號單純記錄節(jié)點值這也是字符串“足夠緊湊”的關鍵原因。3. deserialize 的核心邏輯funcbuild(_min:Int,_max:Int)-TreeNode?這是整個算法的精髓。含義是當前子樹中合法節(jié)點值必須在(min, max)區(qū)間內(nèi)如果當前值不在區(qū)間內(nèi)說明它屬于別的子樹直接返回 nil如果合法就創(chuàng)建節(jié)點并遞歸構(gòu)建左右子樹因為index是全局遞增的所以每個節(jié)點只會被處理一次。4. 為什么不需要回退 index這是很多人一開始想不通的點。原因在于前序遍歷是嚴格的「根 → 左 → 右」一旦某個值不在當前區(qū)間它一定屬于后續(xù)的右子樹或祖先節(jié)點所以不能消費就不動 index這是 BST 性質(zhì)帶來的好處。示例測試及結(jié)果我們用示例一來跑一遍letcodecCodec()letrootTreeNode(2)root.leftTreeNode(1)root.rightTreeNode(3)letdatacodec.serialize(root)print(序列化結(jié)果:,data)letnewRootcodec.deserialize(data)print(反序列化完成根節(jié)點:,newRoot?.val??-1)輸出結(jié)果序列化結(jié)果: 2,1,3 反序列化完成根節(jié)點: 2對于空樹print(codec.serialize(nil))// print(codec.deserialize()nil)// true結(jié)果也是符合預期的。時間復雜度序列化每個節(jié)點訪問一次O(n)反序列化每個節(jié)點構(gòu)建一次O(n)總體時間復雜度O(n)空間復雜度序列化字符串占 O(n)遞歸調(diào)用棧最壞 O(n)退化成鏈表總體空間復雜度O(n)總結(jié)LeetCode 449 是一道非常經(jīng)典的「理解型」題目。它并不難寫但非?？疾炷闶欠裾嬲斫饬薆ST 的結(jié)構(gòu)特性遍歷順序和樹結(jié)構(gòu)之間的關系如何用“約束條件”減少冗余數(shù)據(jù)