331.|331. 验证二叉树的前序序列化 331.验证二叉树的前序序列化

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
9
/
3 2
/ \ /
4 1 # 6
/ \ / \ / \
# # # # 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

二叉树具有递归结构，所以可以考虑用递归的方式来求解。根据二叉树的规律（空节点的数量始终比节点的数量大1）我们可以从整棵树的前序遍历中分离出两棵子树的前序遍历，然后递归调用。
分离子树除去第一个根，从第二个元素开始找出最短的符合二叉树规律的子串，就是左子树的前序遍历。剩下的部分是右子树的前序遍历。
递归终止

如果前序遍历为空，返回False
如果前序遍历长度为1，且是#，返回True
如果前序遍历长度为1，且不是#，返回False
如果前序遍历长度大于1，且根节点是#，返回False

【331.|331. 验证二叉树的前序序列化】算法复杂度取决于树的结构。最坏情况下，如果树成线性结构，空间和时间复杂度为O(n^2)，对于较为平衡二叉树则有空间时间复杂度O(nlogn)。

class Solution: def isValidSerialization(self, preorder: str) -> bool: preorder_list = preorder.split(',') return self.helper(preorder_list)def helper(self, preorder): # termination conditions # 1. empty # 2. preorder is '#' # 3. preorder has a length of 1, #but not '#' # 4. preorder has length greater #than 1, but not start with '#' if preorder == []: return False if len(preorder) == 1: if preorder[0] == '#': return True else: return Falseif preorder[0] == '#': return False# get the preorder of left subtree idx = 1 empty_node_expected = 1 empty_node_seen = 0 while idx < len(preorder): if preorder[idx] == '#': empty_node_seen += 1 if empty_node_seen == empty_node_expected: break else: empty_node_expected += 1 idx += 1# if the right substree preorder is # empty, just return False if idx == len(preorder): return Falseleft_subtree_preorder = preorder[1: idx + 1] right_subtree_preorder = preorder[idx + 1:] return self.helper(left_subtree_preorder) and self.helper(right_subtree_preorder)