本篇推文共計2000個字，閱讀時間約3分鐘。

01

題目描述

題目描述：

給定一串以逗號分隔的序列，

驗證它是否是正確的二叉樹的前序序列化。

編寫一個在不重構(gòu)樹的條件下的可行算法。

序列化二叉樹的一種方法是使用前序遍歷。

當我們遇到一個非空節(jié)點時，我們可以記錄下這個節(jié)點的值。如果它是一個空節(jié)點，我們可以使用一個標記值記錄，例如 #。

例如，上面的二叉樹可以被序列化為
字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，
其中 # 代表一個空節(jié)點。

每個以逗號分隔的字符或為一個整數(shù)或為一個表示 null 指針的 '#' 。

你可以認為輸入格式總是有效的，例如它永遠不會包含兩個連續(xù)的逗號，比如"1,,3"。

示例：

輸入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
輸出: true

輸入: "1,#"
輸出: false

輸入: "9,#,#,1"
輸出: false

02

方法和思路

我們可以用入度和出度的方法來解決本題。

所有節(jié)點的入度之和等于出度之和。

可以根據(jù)這個特點來判斷輸入序列是否為有效的。

我們用一個例子解釋上面的意思，

如下圖所示，是一個二叉樹：

節(jié)點1的出度為2，入度為0
節(jié)點2，5的出度為2，入度為1
節(jié)點3，4，6，7的出度為2，入度為1
空節(jié)點#的出度為0，入度為1
所有節(jié)點的出度和為14
所有節(jié)點的入度和為14

即二叉樹中所有節(jié)點的入度之和等于出度之和

我們只要把字符串利用遍歷的方式，遍歷一次，
計算每個節(jié)點的出度和入度之差diff，
即diff=出度-入度

在遍歷到任何一個節(jié)點的時候，

要求diff>=0,原因是還沒遍歷到該節(jié)點的子節(jié)點，
所以此時的出度應該大于等于入度。

如果diff<0，則代表出度<入度。此時二叉樹不成立，返回False

我們用代碼表示此題的解法如下：

class Solution(object):
    def isValidSerialization(self, preorder):
        nodes = preorder.split(',')
        diff = 1
        for node in nodes:
            diff -= 1
            if diff < 0:
                return False
            if node != '#':
                diff += 2
        return diff == 0

為什么上面的代碼中 diff 的初始化為 1：

因為，我們加入一個非空節(jié)點時，
都會先減去一個入度，再加上兩個出度。

但是由于根節(jié)點沒有父節(jié)點，所以其入度為 0，出度為 2。

因此 diff 初始化為 1，
是為了在加入根節(jié)點的時候，
先減去一個入度，再加上兩個出度，此時 diff 正好應該是2.

往期回顧

【年終總結(jié)】你好2021，再見2020。

【快速寫好畢業(yè)論文】你不得不知曉的七個常用文獻搜索平臺

【秋招紀實錄】一篇特別正經(jīng)的【騰訊】求職經(jīng)驗分享

【一天一道Leetcode】回文字符串-最少分割次數(shù)

【一天一道Leetcode】用棧實現(xiàn)隊列

【一天一道Leetcode】套信封問題

☆ END ☆

你與世界

只差一個

公眾號

【一天一道Leetcode】驗證二叉樹的前序序列化

01

02