Serialize and Deserialize Binary Tree

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

Arrays and Strings Hard Video Code Solution Java

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 9 months ago

Related Problems

Longest Substring with At Most K Distinct Characters

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

Arrays and Strings Medium Video Code Solution Java

Shortest Unsorted Continuous Subarray

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.

Arrays and Strings Medium Video Code Solution Java

Minimum Window Substring

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.

Arrays and Strings Hard Video Python Code Solution

Sudoko Solver

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.

Arrays and Strings Hard Video Python Code Solution