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

Leecode 145. Post-order traversal of binary trees

Given a binary tree, return its backward traversal.

Example:

Input: [1, null, 2, 3]

Output: [3, 2, 1]

First we need to understand what a binary tree is: we walk through the tree in the same way as we visit the left subtree — the right subtree — the root node. We walk through the tree in the same way as we visit the left subtree or the right subtree until we walk through the entire tree. Therefore, the whole traversal process naturally has the nature of recursion, we can directly use recursive function to simulate this process.

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. If null, go postorder(node.right). If there is still a left node on the Right, continue to go to the left node until you reach the left node on the bottom. Take the third step and then debrand the left node into the array.

  2. Return to the right node, then descript into the array

  3. Discards the root node into the array.

   List<Integer> postorderTraversalList = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return ans;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        postorderTraversalList.add(root.val);
        return ans;
    }

Copy the code

JAVA language version iteration stack: First in last out

Define a stack STK that stores a tree

1. Untag the root node into the array and then run through the left subtree to find the bottom left node.

2. Pop out the last node on the stack

3. If the left node is not empty or the right node is not empty, the node is added to the stack

4. If it is empty, the root node is either the left node or the right node. If the left node exits the stack first, then the left node is detested into the array and the right node is detested until the last root node.

 public static  List<Integer> inorderTraversal2(TreeNode root) {
        //
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> s = new Stack<>();
        s.push(root);

        while( !s.isEmpty() ) {
            TreeNode node = s.pop(); // 1. Push root
            if(node.left ! =null) {
                s.push(node.left); // 2. Push 2,null,null
            }

            if(node.right ! =null) {
                s.push(node.right); // 3. Stack 3,null,null
            }

            list.add(0, node.val); // Insert 1, 3, 2 from the end to print 2, 1, 3
        }
        return list;
    }
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! ❤ ️ ❤ ️ ❤ ️ ❤ ️