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

Offer 37. Serialize binary tree

The title

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

Methods a

Pre-traversal: Pre-traversal is used to store node values and null nodes as strings, where null nodes are represented by & and separated by #. To restore the binary tree, do the preorder traversal again.

/** * 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) { return dfs1(root); } String dfs1(TreeNode root) { if (root == null) return "&#"; String res = String.valueOf(root.val) + "#"; res += dfs1(root.left); res += dfs1(root.right); return res; } String data; // Decodes your encoded data to tree. public TreeNode deserialize(String _data) { data = _data; return dfs2(); } TreeNode dfs2() { int i = 0; while(data.charAt(i) ! = '#') i ++; String num = data.substring(0, i); if (i < data.length() - 1) data = data.substring(i + 1); if (num.equals("&")) return null; TreeNode root = new TreeNode(Integer.parseInt(num)); root.left = dfs2(); root.right = dfs2(); return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));Copy the code

Time complexity: O(n)

Space complexity: O(n)

Note: if the preceding traversal contains null nodes, a binary tree can be uniquely identified

The sword refers to Offer 38. Arrangement of strings

The title

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 no repeating elements.

Example:

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

Limitations:

  • 1 <= length of s <= 8

Methods a

Back: in order to prevent repeating elements, such as, a1 = ‘a’, a2 = ‘a’, the results appear in the a1a2, a2a1 situation, to repeat a sequence provided between elements, which is located in the front of the only when the repetition element used to use the back;

class Solution { List<String> res = new LinkedList<>(); String path = ""; char[] c; boolean[] st; public String[] permutation(String s) { c = s.toCharArray(); Arrays.sort(c); st = new boolean[c.length]; dfs(0); return res.toArray(new String[res.size()]); } void dfs(int index) { if (index == c.length) { res.add(path); return ; } for (int i = 0; i < c.length; i ++ ) { if (i ! = 0 && c[i] == c[i - 1] && ! st[i - 1]) continue; If (! st[i]) { path += c[i]; st[i] = true; dfs(index + 1); st[i] = false; path = path.substring(0, path.length() - 1); }}}}Copy the code