序列化二叉樹的一種方法是使用前序遍歷。當(dāng)我們遇到一個(gè)非空節(jié)點(diǎn)時(shí)，我們可以記錄下這個(gè)節(jié)點(diǎn)的值。如果它是一個(gè)空節(jié)點(diǎn)，我們可以使用一個(gè)標(biāo)記值記錄，例如 #。
9
/
3 2
/ \ /
4 1 # 6
/ \ / \ / \

# # # #

例如，上面的二叉樹可以被序列化為字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一個(gè)空節(jié)點(diǎn)。
給定一串以逗號(hào)分隔的序列，驗(yàn)證它是否是正確的二叉樹的前序序列化。編寫一個(gè)在不重構(gòu)樹的條件下的可行算法。
每個(gè)以逗號(hào)分隔的字符或?yàn)橐粋€(gè)整數(shù)或?yàn)橐粋€(gè)表示 null 指針的 '#' 。
你可以認(rèn)為輸入格式總是有效的，例如它永遠(yuǎn)不會(huì)包含兩個(gè)連續(xù)的逗號(hào)，比如 "1,,3" 。
輸入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
輸出: true

二叉樹具有遞歸結(jié)構(gòu)，所以可以考慮用遞歸的方式來求解。根據(jù)二叉樹的規(guī)律（空節(jié)點(diǎn)的數(shù)量始終比節(jié)點(diǎn)的數(shù)量大1）我們可以從整棵樹的前序遍歷中分離出兩棵子樹的前序遍歷，然后遞歸調(diào)用。

分離子樹

除去第一個(gè)根，從第二個(gè)元素開始找出最短的符合二叉樹規(guī)律的子串，就是左子樹的前序遍歷。剩下的部分是右子樹的前序遍歷。

遞歸終止

1. 如果前序遍歷為空，返回False
2. 如果前序遍歷長(zhǎng)度為1，且是#，返回True
3. 如果前序遍歷長(zhǎng)度為1，且不是#，返回False
4. 如果前序遍歷長(zhǎng)度大于1，且根節(jié)點(diǎn)是#，返回False

算法復(fù)雜度取決于樹的結(jié)構(gòu)。最壞情況下，如果樹成線性結(jié)構(gòu)，空間和時(shí)間復(fù)雜度為O(n^2)，對(duì)于較為平衡二叉樹則有空間時(shí)間復(fù)雜度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)