Skip to Content

Serialize and Deserialize Binary Tree

Home | Coding Interviews | Arrays and Strings | Serialize and Deserialize Binary Tree

Design an algorithm to serialize and deserialize a binary tree into a string.

public class Codec {

// Encodes a tree to a single string.

public String serialize(TreeNode root) {
    if(root == null){
        return "";
    }
    
    return dfs(root);
}

StringBuilder sb = new StringBuilder();
public String dfs(TreeNode node){
    if(node == null){
        sb.append("null, ");
        return "";
    }
    
    sb.append(node.val + ", ");
    
    dfs(node.left);
    dfs(node.right);
    
    return sb.toString();
}



// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if(data.equals("")){
        return null;
    }
    String arr[] = data.split(", ");
    return construct(arr);
}

int idx = 0;
public TreeNode construct(String arr[]){
    if(idx >= arr.length || arr[idx].equals("null")){
        idx++;
        return null;
    }
    
    TreeNode node = new TreeNode(Integer.parseInt(arr[idx++]));
    node.left = construct(arr);
    node.right = construct(arr);
    
    return node;
}

Posted by Jamie Meyer 3 months ago

Related Problems

Given a string S and an integer K, return the length of the longest substring of S that contains at most K distinct characters.

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

Given two strings s and t of lengths m and n respectively, return the minimum window

substringof s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.

Each of the digits 1-9 must occur exactly once in each column.

Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.