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

算法复杂度取决于树的结构。最坏情况下，如果树成线性结构，空间和时间复杂度为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 False
        
        if 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 False

        left_subtree_preorder = preorder[1: idx + 1]
        right_subtree_preorder = preorder[idx + 1:]
        return self.helper(left_subtree_preorder) and self.helper(right_subtree_preorder)

最后编辑于：2021.03.12 06:41:45