【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

😄


  \color{red}{~}

Then do it! This column is all about the topic of binary trees, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. The content of binary tree is not much, but it is necessary for every programmer to understand the red black tree, B+ tree, LSM tree are very helpful and so on

Leveldb and Rocksdb implemented by WAL+ Lsm-tree

B + tree mysql

(HBASE) – LSM-Tree converts random write to sequential write, supports multiple layers compaction and lookup, and supports write amplification and read amplification

TokuDB –Fractal Tree

There’s more to discover.

  • Sequential traversal in a binary tree – iteration, recursion
  • Binary tree before sequential traversal – iteration, recursion
  • Binary tree after sequential traversal – iteration, recursion
  • Binary tree sequence traversal – iteration, recursion
  • Maximum depth of binary tree – iterative, recursive
  • Symmetric binary tree of binary tree – iteration, recursion
  • Binary tree path sum – iterative, recursive
  • Construct binary tree – iteration and recursion by traversing sequence from middle order to back order
  • The most recent common ancestor of binary trees – iteration, recursion

Leecode 297. Serialization and deserialization of binary trees

Serialization is the operation of converting a data structure or object into consecutive bits, which can then be stored in a file or memory, or transferred over the network to another computer environment, where the original data can be reconstructed in the reverse way.

Please design an algorithm to implement binary tree serialization and deserialization.

There is no limit to the logic that your sequence/deserialization algorithm performs, you just need to ensure that a binary tree can be serialized

Is a string and deserializes the string into the original tree structure.

Tip: The input and output formats are the same as LeetCode currently uses, see LeetCode’s Serialized binary tree format for details. You don’t have to go this way, you can solve the problem in other ways.

Example 1:

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

Output: [1, 2, 3, null, null, 4, 5)

Example 2:

Enter: root = []

Output: []

Example 3:

Enter: root = [1]

Output: [1]

Example 4:

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

Tip:

The number of nodes in the tree is within the range [0, 104]

-1000 <= Node.val <= 1000

Reference code

Define a tree

class TreeNode {
    int val;          / / head node
    TreeNode left;    / / the left subtree
    TreeNode right;   / / right subtree

    TreeNode(intx) { val = x; }}// Test method
 public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        System.out.println("XXXX result =" + preorderTraversal(treeNode));
}        
Copy the code

  1. You know, this is a tree, it’s just represented as an array

    Let’s take this tree as an example

Key points:

The binary tree can be traversed sequentially, serializing to a comma when it encounters an empty subtree, or continuing recursively. So how do we deserialize? First, we need to divide the original sequence according to, to get the list of elements to be traversed first, and then traverse the sequence from left to right:

If the current element is a comma, the current tree is empty

Otherwise, the left subtree of the tree is parsed, and the right subtree is parsed

/** * Binary tree data serialization and deserialization, binary tree is actually stored in memory, once power or shutdown, binary tree data will be lost in memory. * So we need to save binary tree data, a process called persistence or serialization; After saving the binary tree data to disk, you also need to load the binary tree data on disk into memory, a process called deserialization. Empty nodes are denoted by #. Why use # to separate nodes? * If all nodes have the same value and no delimiters are used, different structures will serialize to the same result */
    public static String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        encode(root, sb);
        return sb.toString();
    }

    private static void encode(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(# ",");
        } else {
            sb.append(node.val);
            sb.append(","); encode(node.left, sb); encode(node.right, sb); }}// Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        String[] vs = data.split(",");
        return decode(vs, new int[] {0});
    }

    private static TreeNode decode(String[] vs, int[] idx) {
        if (vs.length == 0 || idx[0] >= vs.length) {
            return null;
        }
        String s = vs[idx[0]];
        idx[0] + +;if ("#".equals(s)) {
            return null;
        } else {
            int val = Integer.valueOf(s);
            TreeNode node = new TreeNode(val);
            node.left = decode(vs, idx);
            node.right = decode(vs, idx);
            returnnode; }}Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️