297 Serialize and Deserialize Binary Tree ✅¶

Leetcode

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.

Example1:

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

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Idea:

Recursion

Time Complexity O(n)

alt alt

C# Solution - Iterative¶

using System;
using System.Collections.Generic;
using System.Text;
using Algorithms.Medium;

namespace AlgorithmTests.Medium
{
  public class SerializeAndDeserializeBinaryTree
  {
    public string Serialize(TreeNode root)
    {
      if (root == null) return "";

      var sb = new StringBuilder();
      var nodeQueue = new Queue<TreeNode>();

      nodeQueue.Enqueue(root);

      while (nodeQueue.Count > 0)
      {
        var node = nodeQueue.Dequeue();
        if (node == null)
        {
          sb.Append('#');
        }
        else
        {
          sb.Append(node.val + " ");
          nodeQueue.Enqueue(node.left);
          nodeQueue.Enqueue(node.right);
        }
      }
      return sb.ToString();
    }

    public TreeNode DeSerialize(string data)
    {
      if (data.Equals('#')) return null;

      var nodes = data.Split(' ');
      TreeNode root = null;
      var nodeQueue = new Queue<TreeNode>();

      for (var i = 0; i < nodes.Length; i++)
      {
        if (nodeQueue.Count == 0)
        {
          root = new TreeNode(int.Parse(nodes[i]));
          nodeQueue.Enqueue(root);
        }
        else
        {
          TreeNode left = null;
          TreeNode right = null;
          if (!nodes[i].Equals('#'))
          {
            left = new TreeNode(Int32.Parse(nodes[i]));
            nodeQueue.Enqueue(left);
          }
          if (!nodes[i + 1].Equals('#'))
          {
            right = new TreeNode(Int32.Parse(nodes[i + 1]));
            nodeQueue.Enqueue(right);
          }

          TreeNode parent = nodeQueue.Peek();
          parent.left = left;
          parent.right = right;

          i++;
        }
      }

      return root;
    }
  }
}

Recursive¶

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString().trim();
    }
    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("# ");
        }
        else {
            sb.append(node.val+ " ");
            serialize(node.left, sb);
            serialize(node.right, sb);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(" ");
        return deserialize(nodes, new int[]{0});
    }
    private TreeNode deserialize(String[] nodes, int[] index) {
        if (nodes[index[0]].equals("#")) {
            index[0] ++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(nodes[index[0]]));
        index[0] ++;
        node.left = deserialize(nodes, index);
        node.right = deserialize(nodes, index);
        return node;
    }
}

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

1. Serialize and Deserialize BST

297 Serialize and Deserialize Binary Tree ✅¶

C# Solution - Iterative¶

Recursive¶

Related Problems¶