二分木

258.バイナリツリーのプレオーダーシリアル化を確認します



258 Verify Pre Order Serialization Binary Tree



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

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



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

コンマで区切られた各文字は、整数またはnullポインタを表す「＃」のいずれかです。



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

例1：

入力： '9,3,4、＃、＃、1、＃、＃、2、＃、6、＃、＃'
出力：true
例2：



入力：「1、＃」
出力：false
例3：

入力： '9、＃、＃、1'
出力：false

ソース：LeetCode
リンク：https：//leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree
著作権は控除ネットワークに帰属します。商業的転載の公式認可に連絡し、非商業的転載の出典を示してください。
エム
画像

class Solution { public boolean isValidSerialization(String preorder) { if(preorder.charAt(preorder.length() - 1) != '#'){ return false } if(preorder.length() == 0){ return true } if(preorder.length() == 1 && preorder.charAt(0) == '#'){ return true } if(preorder.length() == 1){ return false } String []tems = preorder.split(',') Stack stack = new Stack() for (int i = 0 i

画像