This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【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

Leecode 102. Sequence traversal of binary trees

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

Example: binary tree: [3,9,20,null,null,15,7],

Return the sequence traversal result:

[[3], [9,20], [15,7]

Sequential traversal, as the name suggests, is layer by layer, top to bottom, left to right.

At this point, let’s think can we do that with a stack?

Because the stack is fifo, but we’re asking for a sequential traversal, which is obviously fifO

Then you use the queue data structure because it’s first in, first out.

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("X order traversal result =" + preorderTraversal(treeNode));
}        
Copy the code

JAVA language version recursion

  1. Dequeue the entire tree.

  2. Take out the tree and add the root node to the array.

  3. If the left node of the tree is not empty, it adds to the track queue, and if the right node is not empty, it adds to the track queue.

4. If the queue is not empty, pop the first one in, add the root node to the array, and return to step 3.

  1. Discards the root node into the array.
  public static List<List<Integer>> levelOrder(TreeNode root) {
         List<List<Integer>> listList = new ArrayList<>();
         if(root == null) {
             return listList;
         }
         Queue<TreeNode> queue = new LinkedList<>();  // Queue is first in first out (FIFO)
         queue.add(root);
         while(! queue.isEmpty()) {int size = queue.size();
             List<Integer> list = new ArrayList<>();
             while(size > 0) {
                 TreeNode tempNode = queue.poll();
                 list.add(tempNode.val);
                 if(tempNode.left ! =null) {
                     queue.add(tempNode.left);
                 }
                 if(tempNode.right ! =null) {
                     queue.add(tempNode.right);
                 }
                 size--; // Traverse from top to bottom, left to right one by one
             }
             listList.add(list);
         }
         return listList;
     }

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! ❤ ️ ❤ ️ ❤ ️ ❤ ️