二分木の事前シリアル化を確認します
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