Original link: leetcode-cn.com/problems/se…

Answer:

  1. Refer to a “hand painted illustration” analysis | DFS and BFS method of binary tree serialization and deserialization.
  2. It’s not really a strict requirement to serialize the binary tree to[1, 2, 3, null, null, 4, 5)As long as the output is1, 2, X, X, 3, 4, X, X, 5 X, X(X means null), and re-deserialize to a binary tree.
  3. Serialization:
    • DFS is used to traverse each node.
    • If an empty node is encountered, X is returned.
    • If the node has a value, it and the left and right subtrees are concatenated into a string in the order of root, left, and right.
  4. Deserialization:
    • Since we have serialized the binary tree in the order root, left, and right, we can recursively generate the binary tree in that order.
    • Converting a serialized string into an array, one value at a time, ensures the order of root, left, and right.
    • If the outbound value is X, a NULL is generated and returned.
    • If a normal value is queued out, a node is created with it and joined to a binary tree with the recursively generated left and right subtrees.
/** * 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) {
  // If the node is empty, use a specific character to identify it
  if(! root) {return 'X';
  }

  // Each recursion gets the serialized results of the left and right subtrees
  const left = serialize(root.left);
  const right = serialize(root.right);

  // Splice the current binary tree to the root, left, and right
  return `${root.val}.${left}.${right}`;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}* /
var deserialize = function(data) {
  // Convert the serialized string to an array
  const valList = data.split(', ');

  // Generate binary tree method
  function build() {
    // Since the binary tree is already serialized in root, left, and right order, each recursion only needs to fetch the values of each node in order
    const val = valList.shift();

    // If the current value is X, this object is empty and null is returned
    if (val === 'X') {
      return null;
    }

    // Generate a node with the current value
    const node = new TreeNode(val);

    // Connect the child nodes to the root node in the same order since the child nodes are removed from the left after the right
    node.left = build();
    node.right = build();

    // Return the currently generated node for the next level of recursive spanning tree
    return node;
  }

  return build();
};
Copy the code