Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- public class Codec {
- // Decodes your encoded data to tree.
- public TreeNode deserialize(String data) {
- String[] stringNodes = data.split(",");
- List<Integer> traversal = new ArrayList<Integer>();
- for (int i = 0; i < stringNodes.length; i++) {
- String node = stringNodes[i];
- if (node.equals("null")) {
- traversal.add(null);
- } else if (!node.isEmpty()) {
- traversal.add(Integer.parseInt(node));
- }
- }
- TreeNode root = null;
- if (traversal.size() > 0) {
- root = new TreeNode(traversal.get(0));
- int index = 1;
- Queue<TreeNode> queue = new ArrayDeque();
- queue.offer(root);
- while (!queue.isEmpty()) {
- for (int i = 0; i < queue.size(); i++) {
- TreeNode node = queue.poll();
- if (index < traversal.size()) {
- Integer leftVal = traversal.get(index);
- if (leftVal != null) {
- node.left = new TreeNode(leftVal);
- queue.offer(node.left);
- }
- index += 1;
- }
- if (index < traversal.size()) {
- Integer rightVal = traversal.get(index);
- if (rightVal != null) {
- node.right = new TreeNode(rightVal);
- queue.offer(node.right);
- }
- index += 1;
- }
- }
- }
- }
- return root;
- }
- // Encodes a tree to a single string.
- public String serialize(TreeNode root) {
- // gettings traversal
- List<Integer> traversal = levelOrderTraversalWithNulls(root);
- // trim
- for (int i = traversal.size() - 1; i >= 0; i--) {
- if (traversal.get(i) != null) break;
- traversal.remove(i);
- }
- // building string
- StringBuilder sb = new StringBuilder();
- for (int i = 0; i < traversal.size(); i++) {
- sb.append(traversal.get(i));
- if (i != traversal.size() - 1) {
- sb.append(",");
- }
- }
- System.out.println(sb.toString());
- return sb.toString();
- }
- private List<Integer> levelOrderTraversalWithNulls(TreeNode root) {
- List<Integer> result = new ArrayList<Integer>();
- Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
- if (root != null) {
- queue.offer(root);
- result.add(root.val);
- }
- while (!queue.isEmpty()) {
- for (int i = 0; i < queue.size(); i++) {
- TreeNode node = queue.poll();
- result.add(node.left == null ? null : node.left.val);
- result.add(node.right == null ? null : node.right.val);
- if (node.left != null) {
- queue.offer(node.left);
- }
- if (node.right != null) {
- queue.offer(node.right);
- }
- }
- }
- return result;
- }
- }
- // Your Codec object will be instantiated and called as such:
- // Codec codec = new Codec();
- // codec.deserialize(codec.serialize(root));
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement