二分木の事前シリアル化を確認します



Verify Pre Serialization Binary Tree



二分木をシリアル化する1つの方法は、プレオーダートラバーサルを使用することです。空でないノードに遭遇した場合、このノードの値を記録できます。空のノードの場合は、たとえば#などのタグ値レコードを使用できます。

9 / 3 2 / / 4 1 # 6 / / / # # # # # #

たとえば、上記の二分木は、文字列'9,3,4,#,#,1,#,#,2,#,6,#,#'にシリアル化できます。空のノードを表します。



カンマ区切りのシーケンスのシーケンスが与えられた場合、それがバイナリツリーの正しいシリアル化であることを確認します。ツリーをリファクタリングせずに実行可能なアルゴリズムを記述します。

コンマで区切られた各文字は、整数または表現のいずれかです#ポインターnull



入力形式は常に有効であると考えることができます。たとえば、'#'のように2つの連続したコンマが含まれることはありません。 。

例1:

'1,,3'

例2:



Input: '9,3,4,#,#,1,#,#,2,#,6,#,#' Output: true

例3:

Input: '1,#' Output: false

トピック分析:

指定されたシリアル化された文字列は、事前順序でトラバースされる完全な二分木であり、ターミナルノードは「#」に置き換えられるため、各ノード(ターミナルノードを除く)の次数は2である必要があります。

コード:

Input: '9,#,#,1' Output: false

メイン機能:

public boolean isValidSerialization(String preorder) { String[] str = preorder.split(',') int dif = 1 for (String s : str) { if (--dif < 0) return false if (!s.equals('#')) dif += 2 } return dif == 0 }

演算結果:

true
true
false