難度:
中等
題目描述:
序列化二叉樹的一種方法是使用前序周遊。當我們遇到一個非空節點時,我們可以記錄下這個節點的值。如果它是一個空節點,我們可以使用一個标記值記錄,例如
#。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLwIlblxmUXRmc5cVWv5kMMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLzcTM5QDN1QTMyEzMwEjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
例如,上面的二叉樹可以被序列化為字元串 “9,3,4,#,#,1,#,#,2,#,6,#,#”,其中 # 代表一個空節點。
給定一串以逗号分隔的序列,驗證它是否是正确的二叉樹的前序序列化。編寫一個在不重構樹的條件下的可行算法。
每個以逗号分隔的字元或為一個整數或為一個表示 null 指針的 ‘#’ 。
你可以認為輸入格式總是有效的,例如它永遠不會包含兩個連續的逗号,比如 “1,3” 。
示例 1:
輸入: “9,3,4,#,#,1,#,#,2,#,6,#,#” 輸出: true
示例 2:
輸入: “1,#” 輸出: false
示例 3:
輸入: “9,#,#,1” 輸出: false
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
class Solution {
public:
int n;
bool isValidSerialization(string preorder) {
n = preorder.size();
int cnt = 0;
int num = 0;
for(int i=0; i<n; i++) {
if(isdigit(preorder[i])) {
num = 1;
}
else if(preorder[i] == ',') {
cnt += num;
if(cnt < 0 && i != n-1)
return false;
}
else if(preorder[i] == '#') {
num = -1;
}
}
return cnt+num == -1;
}
};