[TOC] ## 題目描述 題目leetcode331地址：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/ 序列化二叉樹的一種方法是使用前序遍歷。當我們遇到一個非空節點時，我們可以記錄下這個節點的值。如果它是一個空節點，我們可以使用一個標記值記錄，例如 #。 ``` _9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # # ``` 例如，上面的二叉樹可以被序列化為字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一個空節點。 給定一串以逗號分隔的序列，驗證它是否是正確的二叉樹的前序序列化。編寫一個在不重構樹的條件下的可行算法。 每個以逗號分隔的字符或為一個整數或為一個表示 null 指針的 '#' 。 你可以認為輸入格式總是有效的，例如它永遠不會包含兩個連續的逗號，比如 "1,,3" 。 示例 1: ``` 輸入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 輸出: true ``` ## 解題 ### 方法一，填充槽位 二叉樹的建立也伴隨著槽位數量的變化。每當遇到一個節點時： * 如果遇到了空節點，則要消耗一個槽位； * 如果遇到了非空節點，則除了消耗一個槽位外，還要再補充兩個槽位 >此外，還需要將根節點作為特殊情況處理。 具體步驟如下： 1. 初始化槽位 `slot=1`，放置根節點的槽 2. 遍歷，當字符串等于`','`時，上一個節點占用一個槽位， `slot--` 3. 如果`slot<0`， 直接返回false。沒有槽位可以放置節點了。 4. 判斷上一個節點是否為空節點，如果為空則占用一個槽位，如果不為空，則需要兩個槽位。葉子節點需要兩個槽 5. 遍歷完畢，查看最后節點如果是空節點，，則槽的數量-1， slot--；如果最后節點不為空，則槽的數量+1， slot++。 6. 如果槽位等于0，則是有效二叉樹。否則，則不是有效二叉樹。 ```cpp bool test() { std::string a = "9,3,4,#,#,1,#,#,2,#,6,#,#"; int n = a.length(); int slot = 1; //放置根節點的槽 for (size_t i = 0; i < n; i++) { if (a.at(i) == ',') { slot --; //填充一個槽， 槽的數量-1 if (slot < 0) return false; //如果槽的數量<0則返回false if (a.at(i-1) != '#') slot+=2; //如果上一個節點不是空節點，則添加兩個槽，葉子節點需要兩個槽 } } if(a.at(n-1) == '#') slot--; //最后一個節點如果是空，槽的數量-1 else slot++; //最后一個節點如果不是是空， 槽的數量 + 1 return slot == 0; } ```