Question

Formatted question description: https://leetcode.ca/all/297.html

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].
-1000 <= Node.val <= 1000

Algorithm

Pre-order traversal method.

For serialization, we start from the root node. If the node exists, store the value in the output string stream, and then recursively call the serialization function on its left and right child nodes.

For deserialization, we first read in the first character to generate a root node, and then recursively call the deserialization function on the left and right child nodes of the root node.

Code

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Serialize_and_Deserialize_Binary_Tree {

    public static void main(String[] args) {
        Serialize_and_Deserialize_Binary_Tree out = new Serialize_and_Deserialize_Binary_Tree();
        Codec_bfs s = out.new Codec_bfs();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

//        System.out.println(s.serialize(root)); // 1,2,X,X,3,4,X,X,5,X,X,
//
//        System.out.println(s.deserialize("1,2,X,X,3,4,X,X,5,X,X,").val);

        System.out.println(s.serialize(root)); // 1,2,3,X,X,4,5,X,X,X,X,

        System.out.println(s.deserialize("1,2,3,X,X,4,5,X,X,X,X,").val);
    }

    // dfs
    public class Codec {
        private static final String spliter = ",";
        private static final String nullNode = "X";

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            buildString(root, sb);
            return sb.toString();
        }

        // pre-order traversal
        private void buildString(TreeNode node, StringBuilder sb) {
            if (node == null) {
                sb.append(nullNode).append(spliter);
            } else {
                sb.append(node.val).append(spliter);
                buildString(node.left, sb);
                buildString(node.right, sb);
            }
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            LinkedList<String> nodesList = new LinkedList<>();
            nodesList.addAll(Arrays.asList(data.split(spliter)));
            return buildTree(nodesList);
        }

        private TreeNode buildTree(LinkedList<String> nodes) {
            String val = nodes.removeFirst();
            if (val.equals(nullNode)) {
                return null;
            } else {
                TreeNode node = new TreeNode(Integer.parseInt(val));
                node.left = buildTree(nodes);
                node.right = buildTree(nodes);

                return node;
            }
        }
    }

/*
     1
    / \
   2   3
      / \
     4   5

 as "[1,2,3,null,null,4,5]"

for each parent with index-i, its children index:
    left: 2*i+1
    right: 2*i+2
 */
    public class Codec_bfs {

        private static final String spliter = ",";
        private static final String nullNode = "X";

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {

            if(root == null) {
                return "";
            }

            Queue<TreeNode> q = new LinkedList<>();

            StringBuilder result = new StringBuilder();

            q.offer(root);
            while(!q.isEmpty()) {
                TreeNode current = q.poll();
                if (current != null) {
                    result.append(current.val).append(spliter);
                    q.offer(current.left);
                    q.offer(current.right);
                } else {
                    result.append(nullNode).append(spliter);
                }
            }

            return result.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {

            String[] nodes = data.split(spliter);

            TreeNode root = null;

            for (int i = 0; 2 * i + 2 < nodes.length; i++) {

                if (nodes[i].equals(nullNode)) {
                    continue;
                }

                TreeNode current = new TreeNode(Integer.parseInt(nodes[i]));

                if (!nodes[2 * i + 1].equals(nullNode)) {
                    current.left = new TreeNode(Integer.parseInt(nodes[2 * i + 1]));
                }

                if (2*i+2 < nodes.length && !nodes[2 * i + 2].equals(nullNode)) {
                    current.right = new TreeNode(Integer.parseInt(nodes[2 * i + 2]));
                }

                if (i == 0) {
                    root = current;
                }

            }
            return root;
        }
    }

}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private static final String NULL = "#";
    private static final String SEP = ",";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }

    private void preorder(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL + SEP);
            return;
        }
        sb.append(root.val + SEP);
        preorder(root.left, sb);
        preorder(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || "".equals(data)) {
            return null;
        }
        List<String> vals = new LinkedList<>();
        for (String x : data.split(SEP)) {
            vals.add(x);
        }
        return deserialize(vals);
    }

    private TreeNode deserialize(List<String> vals) {
        String first = vals.remove(0);
        if (NULL.equals(first)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(vals);
        root.right = deserialize(vals);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

// OJ: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
class Codec {
private:
    TreeNode *getNode(vector<string> &v, int &i) {
        string s = v[i++];
        return s == "#" ? NULL : new TreeNode(stoi(s));
    }
public:
    string serialize(TreeNode* root) {
        if (!root) return "";
        queue<TreeNode*> q;
        q.push(root);
        string ans;
        while (!q.empty()) {
            root = q.front();
            q.pop();
            if (!ans.empty()) ans += ',';
            if (root) {
                ans += to_string(root->val);
                q.push(root->left);
                q.push(root->right);
            } else ans += '#';
        }
        return ans;
    }
    TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;
        stringstream ss(data);
        string val;
        vector<string> v;
        while (getline(ss, val, ',')) v.push_back(val);
        TreeNode *root = new TreeNode(stoi(v[0]));
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;
        while (i < v.size()) {
            TreeNode *node = q.front();
            q.pop();
            node->left = getNode(v, i);
            node->right = getNode(v, i);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return root;
    }
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """

        if root is None:
            return ''
        res = []

        def preorder(root):
            if root is None:
                res.append("#,")
                return
            res.append(str(root.val) + ",")
            preorder(root.left)
            preorder(root.right)

        preorder(root)
        return ''.join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        vals = data.split(',')

        def inner():
            first = vals.pop(0)
            if first == '#':
                return None
            return TreeNode(int(first), inner(), inner()) # seems using a constructor __init__(val, left, right)

        return inner()


# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

############

from collections import deque

# bfs, each level based
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        ret = []
        queue = deque([root])
        while queue:
            top = queue.popleft()
            if not top:
                ret.append("None")
                continue
            else:
                ret.append(str(top.val))
            queue.append(top.left)
            queue.append(top.right)
        return ",".join(ret)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        data = data.split(",")
        if data[0] == "None":
            return None
        root = TreeNode(int(data[0]))
        queue = deque([root])
        i = 0
        while queue and i < len(data):
            top = queue.popleft()
            i += 1
            left = right = None
            if i < len(data) and data[i] != "None":
                left = TreeNode(int(data[i]))
                queue.append(left)
            i += 1
            if i < len(data) and data[i] != "None":
                right = TreeNode(int(data[i]))
                queue.append(right)

            top.left = left
            top.right = right

        return root

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/*
 * Encodes a tree to a single string.
 */
function serialize(root: TreeNode | null): string {
    if (root == null) {
        return '#';
    }
    const { val, left, right } = root;
    return `${val},${serialize(left)},${serialize(right)}`;
}

/*
 * Decodes your encoded data to tree.
 */
function deserialize(data: string): TreeNode | null {
    const n = data.length;
    if (n === 1) {
        return null;
    }
    const vals = data.split(',').reverse();
    const renew = () => {
        const val = vals.pop();
        if (val == null || val === '#') {
            return null;
        }
        return new TreeNode(Number(val), renew(), renew());
    };
    return renew();
}

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
    return rserialize(root, '');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
    const dataArray = data.split(',');
    return rdeserialize(dataArray);
};

const rserialize = (root, str) => {
    if (root === null) {
        str += '#,';
    } else {
        str += root.val + '' + ',';
        str = rserialize(root.left, str);
        str = rserialize(root.right, str);
    }
    return str;
};

const rdeserialize = dataList => {
    if (dataList[0] === '#') {
        dataList.shift();
        return null;
    }

    const root = new TreeNode(parseInt(dataList[0]));
    dataList.shift();
    root.left = rdeserialize(dataList);
    root.right = rdeserialize(dataList);

    return root;
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
struct Codec {

}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl Codec {
    fn new() -> Self {
        Codec {}
    }

    fn serialize(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
        if root.is_none() {
            return String::from("#");
        }
        let mut node = root.as_ref().unwrap().borrow_mut();
        let left = node.left.take();
        let right = node.right.take();
        format!(
            "{},{},{}",
            self.serialize(right),
            self.serialize(left),
            node.val
        )
    }

    fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
        if data.len() == 1 {
            return None;
        }
        Self::renew(&mut data.split(",").collect())
    }

    fn renew(vals: &mut Vec<&str>) -> Option<Rc<RefCell<TreeNode>>> {
        let val = vals.pop().unwrap_or("#");
        if val == "#" {
            return None;
        }
        Some(Rc::new(RefCell::new(TreeNode {
            val: val.parse().unwrap(),
            left: Self::renew(vals),
            right: Self::renew(vals),
        })))
    }
}

/**
 * Your Codec object will be instantiated and called as such:
 * let obj = Codec::new();
 * let data: String = obj.serialize(strs);
 * let ans: Option<Rc<RefCell<TreeNode>>> = obj.deserialize(data);
 */

297 - Serialize and Deserialize Binary Tree

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions