This is the 30th day of my participation in the August Challenge

Serialize binary trees

Offer 37. Serialize binary tree

Difficulty: difficulty

Leetcode address: leetcode-cn.com/problems/xu…

Implement two functions to serialize and deserialize the binary tree.

You need to design an algorithm to implement binary tree serialization and deserialization. There is no limit to the logic of your sequence/deserialization algorithm, you just need to ensure that a binary tree can be serialized to a string and deserialized to the original tree structure.

Example:

Input: root = [1, 2, 3, null, null, 4, 5) output: [1, 2, 3, null, null, 4, 5)Copy the code

Answer key

A method of BFS

Serialization steps:

  • Create a result array, res, and then use a queue to initially put the root node into the column and examine the resulting node:
    • The exit node is NULL, pushing “$” into res.
    • The exit node is a numeric value, pushing the value into the RES and enlisting its left and right nodes.
  • In, out… Until the queue is empty, all nodes are iterated, the RES is built, and the RES is converted to a string.

Deserialization steps:

The sequence that can be obtained by appeal serialization is 1, 2, 3, $, 4, 5 $$$$. It can be seen that the first node is the root node, and the other nodes are corresponding to the left and right child nodes.

  • The string is converted to an array list, and the cursor is scanned from the second item.
  • List [0] builds the root node and adds the root node to the column.
  • When the node is displayed, the cursor refers to the left child and the cursor refers to the right child. If the child node is “$”, skip; Otherwise (if the child node is numeric), create the node, assign the parent node to the child node, and place that node in the column.
/** * 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) {
  const queue = [root];
  let res = [];
  while(queue.length){
    const node = queue.shift(); // check the exit node
    if(node){										// if the node is not null, the node is added to the column; otherwise, $is added to the column.
      res.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    }else{
      res.push('$'); }}return res.join(', ');					// Array to string
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}* /
var deserialize = function(data) {
	if(data === '$') return null;
  
  const list = data.split(', ');		// Serialize string split into an array
  
  const root = new TreeNode(list[0]);// Build the root node
  const queue = [root];						// The root node is in the column
  let cursor = 1;									// Initializes the second item in the list
  
  while(cursor < list.length){		// The pointer is out of bounds, that is, the serialized string is swept
    const node = queue.shift();		// check the exit node
    
    const leftVal = list[cursor];	// Left node value
    const rightVal = list[cursor+1];// Value of the right node
    
    if(leftVal ! = ='$') {// If the node is not null:
      const leftNode = new TreeNode(leftVal);// Create the left child node
      node.left = leftNode;				// The left child tree of the parent refers to the left child
      queue.push(leftNode);				// it is the parent node
    }
    if(rightVal ! = ='$') {const rightNode = new TreeNode(rightVal);
      node.right = rightNode;							
      queue.push(rightNode);
    }
    cursor += 2;
  }
  return root;
};

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

Method two DFS

Serialization steps:

  • Recursively traverses a tree and concatenates the returned results.
  • Choose to do a front-order traversal (root | left | right) and use “$” instead when a NULL node is encountered.

Deserialization steps:

  • The result of the serialization above is1 2 $$3 4 $$5 $$
  • Define the function buildTree to restore the binary tree, passing in the list array converted from the serialized string.
  • Shift-by-shift builds the root node of the current subtree along the list, root -> left -> right
    • If the pop-up character is $, null is returned
    • If the pop-up character is a numeric value, the root node is created and the left and right subtrees of root are recursively built, finally returning root.
const serialize = (root) = > {
  if(root === null) {return '$';
  }
  const left = serialize(root.left);
  const right = serialize(root.right);
  return root.val + ', ' + left + ', ' + right;
};

const deserialize = (data) = > {
  const list = data.split(', ');
  
  const buildTree = (list) = > {
    const rootVal = list.shift();
    if(rootVal === '$') {return null;
    }
    const root = new TreeNode(rootVal);
    root.left = buildTree(list);
    root.right = buildTree(list);
    return root;
  };
  return buildTree(list);
}
Copy the code

String arrangement

The sword refers to Offer 38. Arrangement of strings

Difficulty: Medium

Leetcode address: leetcode-cn.com/problems/zi…

Enter a string and print out all permutations of the characters in the string.

You can return this array of strings in any order, but there must be no duplicate elements.

Example:

Input: s = "ABC" output: [" ABC ", "acb", "America", "bca", "cab", "cba"]Copy the code

Limitation: 1 <= length of s <= 8

Answer key

The classic backtracking algorithm, in this case is the full permutation + reweight, sorting using backtracking algorithm, reweight here directly using Set, convenient and easy. The classic backtracking algorithm, in this case is the full permutation + reweight, sorting using backtracking algorithm, reweight here directly using Set, convenient and easy. About the backtracking algorithm theory here is recommended to see Carl brother B station teaching video with you to learn through the backtracking algorithm! (Theory), which can quickly help us understand the application scenarios of backtracking algorithm.

Backtracking algorithms (purely violent search) use scenarios: combinations, permutations, cuts, subsets, checkerboards

/ * * *@param {string} s
 * @return {string[]}* /
var permutation = function(s) {
  const res = new Set(a);// Used to remove weight
  const visit = {}
  function dfs(path) {
    if(path.length === s.length) return res.add(path);// Termination conditions
    for (let i = 0; i < s.length; i++) {
      if(! visit[i]){ visit[i] =true;// Tag access
        dfs(path + s[i]);/ / recursion
        visit[i] = false;// Backtrace to remove the flag
      }
    }
  }
  dfs(' ');
  return [...res];
};
Copy the code

Practice every day! The front end is a new one. I hope I can get a thumbs up