Java実装LeetCode 449シーケンス化と逆シーケンス化の二叉検索ツリー
7782 ワード
449.シーケンス化と逆シーケンス化の二叉探索ツリー
シーケンス化は、データ構造またはオブジェクトを一連のカラムビットに変換するプロセスであり、ファイルまたはメモリバッファに格納したり、ネットワーク接続リンクを介して転送したりして、後で同じコンピュータ環境または別のコンピュータ環境で再構築することができます.
二叉探索ツリーをシーケンス化および逆シーケンス化するアルゴリズムを設計した.シーケンス化/逆シーケンス化アルゴリズムの動作には制限はありません.二叉検索ツリーが文字列にシーケンス化され、最初の二叉検索ツリーに逆シーケンス化できることを確認します.
符号化された文字列はできるだけコンパクトにしなければならない.
注意:クラスメンバー/グローバル/静的変数を使用してステータスを格納しないでください.あなたのシーケンス化と逆シーケンス化アルゴリズムは無状態であるべきです.
シーケンス化は、データ構造またはオブジェクトを一連のカラムビットに変換するプロセスであり、ファイルまたはメモリバッファに格納したり、ネットワーク接続リンクを介して転送したりして、後で同じコンピュータ環境または別のコンピュータ環境で再構築することができます.
二叉探索ツリーをシーケンス化および逆シーケンス化するアルゴリズムを設計した.シーケンス化/逆シーケンス化アルゴリズムの動作には制限はありません.二叉検索ツリーが文字列にシーケンス化され、最初の二叉検索ツリーに逆シーケンス化できることを確認します.
符号化された文字列はできるだけコンパクトにしなければならない.
注意:クラスメンバー/グローバル/静的変数を使用してステータスを格納しないでください.あなたのシーケンス化と逆シーケンス化アルゴリズムは無状態であるべきです.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
public int i = 0;
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
doSerialize(root, sb);
return sb.toString();
}
public void doSerialize(TreeNode root, StringBuilder sb) {
if (root == null) {
return;
}
sb.append((char) root.val);
doSerialize(root.left, sb);
doSerialize(root.right, sb);
}
public TreeNode deserialize(String data) {
char[] arr = data.toCharArray();
return doDescrialize(arr, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode doDescrialize(char[] arr, int minValue, int maxValue) {
if (i >= arr.length || (char) arr[i] > maxValue) {
return null;
}
TreeNode root = new TreeNode((char) arr[i++]);
root.left = doDescrialize(arr, minValue, root.val);
root.right = doDescrialize(arr, root.val, maxValue);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));