【3.12】LeetCode每日一题· 验证二叉树的前序序列化

2021年03月12日 11时38分

标签： LeetCode 栈树形结构

## 题目描述
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

_9_
		/   \
	   3     2
	  / \   / \
	 4   1  #  6
	/ \ / \   / \
	# # # #   # #
例如，上面的二叉树可以被序列化为字符串`"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/ "题目链接")

## 解题思路
由于指定了序列化的是一棵**二叉树**，因此每个结点能且仅能提供向下的两个分支。当我们在遍历序列化的二叉树时，如果遇到一个结点，就将当前栈顶结点的**空分支数-1**，并将当前结点压入**栈**中，并记录其有两个分支为空（具体实现时，可以不记录结点而只记录该结点的空的分支的个数）。而遇到`#`时，将栈顶结点的**空分支数-1**即可。如果某一结点没有空分支了，即**空分支数=0**时，就将该结点**弹出栈**。
如果在处理过程中，发现**序列尚未遍历完但栈已为空**，或者**序列已遍历完但栈不为空**，则说明不是合法的二叉树的前序序列化，否则是二叉树的前序序列化。

为了进一步优化空间，可以**把整个栈看作一个整体**，记录当前**所有结点的空分支个数**`num`。如果在处理过程中，发现**序列尚未遍历完但`num`等于0**，或者**序列已遍历完但`num`不为0**，则说明不是合法的二叉树的前序序列化，否则是二叉树的前序序列化。

此外需要注意，输入的是一个字符串，需要将字符串按照`,`分开后，才能得到各个节点，而不能直接使用`preorder[i]`访问结点。

## 代码（栈实现）
	class Solution {
	public:
		string getNext(string& preorder, int& index){
			string temp = "";
			while(index < preorder.length() && preorder[index] != ','){
				temp.push_back(preorder[index++]);
			}
			if(preorder[index] == ',') index++;
			return temp;
		}

bool isValidSerialization(string preorder) {
			stack<int> stk;
			int i = 0;
			string s = getNext(preorder, i);
			if(s != "#") stk.push(2);
			while(!stk.empty() && ((s = getNext(preorder, i)) != "")){
				if(s == "#"){
					if(!stk.empty()) --stk.top();
					while(!stk.empty() && stk.top()==0) stk.pop(); 
				}
				else{
					if(!stk.empty()) --stk.top();
					while(!stk.empty() && stk.top()==0) stk.pop();
					stk.push(2);
				}
			}
			if(stk.empty() && i == preorder.length()) return true;
			return false;
		}
	};

### 用时和内存
> 执行用时：4 ms，在所有 C\++提交中击败了74.27%的用户
> 内存消耗：6.8 MB，在所有 C\++提交中击败了61.79%的用户

## 代码（内存优化）
	class Solution {
	public:
		string getNext(string& preorder, int& index){
			string temp = "";
			while(index < preorder.length() && preorder[index] != ','){
				temp.push_back(preorder[index++]);
			}
			if(preorder[index] == ',') index++;
			return temp;
		}

bool isValidSerialization(string preorder) {
			int cnt = 0, i = 0;
			string s = getNext(preorder, i);
			if(s != "#") cnt += 2;
			while(cnt > 0 && ((s = getNext(preorder, i)) != "")){
				if(s=="#") --cnt;
				else ++cnt;
			}
			if(cnt == 0 && i == preorder.length()) return true;
			return false;
		}
	};

### 用时和内存
> 执行用时：4 ms，在所有 C\++提交中击败了74.27%的用户
> 内存消耗：6.7 MB，在所有 C\++提交中击败了79.92%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.12】LeetCode每日一题· 验证二叉树的前序序列化

所有评论

暂无评论

新增评论