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
  • Binary tree sequence traversal – iteration, recursion
  • Maximum depth of binary tree – iterative, recursive
  • Symmetric binary tree of binary tree – iteration, recursion

Leecode 112. Sum of paths

You are given the root node of the binary tree and an integer targetSum representing the targetSum. Determine if there is a path from the root node to the leaf node in the tree. The sum of all nodes in the path equals the target and targetSum.

A leaf node is a node that has no children.

Input: root = [13,4,7,2 5,4,8,11, null, null, null, null, 1], targetSum = 22

Output: true,

Enter: root = [1,2,3], targetSum = 5

Output: false

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

Find a tree recursively from the top down, subtract the left subtree and the right subtree from the target value sum, and see if it equals nothing.

Because equal to null means that the left or right node of the tree is the last child node.

JAVA language version recursion


  public static  boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) {
            return false;
        }
        if(root.val == sum && root.left == null && root.right == null) {
            return true;
        }
        sum -= root.val;
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);

    }

Copy the code

JAVA language version iteration

The iterative version is also very simple, using stacks or queues

Is it better to think about queue or stack? If the left or right node is not empty, we join the queue. If the left or right node is not empty, we continue to queue. If the sum of the sums equals the target value, the result is true.

  1. Define a queue node and save the tree (FIFO)

  2. Define a queue val to record the cumulative value

  3. Initialize the queue node and add the whole tree to the queue, because I also need to judge by the left or right node of the tree.

  4. Take out the root node and record the accumulated value as the root node

  5. Queue node element, not 0, because we need to determine whether the tree has been traversed

  6. Fetch an element from the queue node, which is the tree to which it was added

  7. From queue val, fetch the root node, which is the cumulative value

8. If the left or right node is empty, it indicates the end, check whether the sum equals the target value, if so return true.

  1. The left node of the extracted tree is not empty. Add the tree with the left node as the root to queue node. The sum of queue val = sum + the root of the left subtree with the left node as the root, which is itself. Go back to step 5 and go down.

  2. The right node of the extracted tree is not empty. Add the tree with the right root to queue node. The sum of queue val = sum + the root of the right subtree with the right root, which is itself. Go back to step 5 and go down.

 class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while(! queNode.isEmpty()) { TreeNode now = queNode.poll();int temp = queVal.poll();
            if (now.left == null && now.right == null) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if(now.left ! =null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if(now.right ! =null) { queNode.offer(now.right); queVal.offer(now.right.val + temp); }}return false; }}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! ❤ ️ ❤ ️ ❤ ️ ❤ ️