Making the warehouse
Online reading address

Here’s what you need to know before you practice

Applicable people

If you’re preparing for an interview and you don’t know where to start with a lot of complicated data structures and algorithms;

If you have learned some basic knowledge of data structures or algorithms before, but do not understand clearly, let alone complete the design of algorithms, want to consolidate this knowledge;

If you have a short period of work experience, but always spend all day in wheels, tuning API, want to take a look at the underlying source code is often due to insufficient programming internal forces and give up;

If you have heard of LeetCode this website, want to brush through to the end, towards the peak of the algorithm, but because of the vast amount of questions and lack of systematic training feel powerless, three days of fishing and two days of exposure to the net, and then feel anxious, even give up……

If any of the above is true for you, you’ve come to the right place. As a well-known front-end blogger in the circle, I would like to share my process of systematic combing and practice with my influence, hoping to help more people who meet with similar difficulties like me, so that you will have less unnecessary trouble.

The language used throughout is JavaScript, so the title says front-end XXX, but in fact, as you know, the data structure and algorithm are mainly a test of one’s thinking, as for the language, it does not use any of the advanced syntax features of JS, as long as some programming experience, can understand the code is completely no problem. You can rest assured of that.

Algorithm doesn’t work, right?

Before I start this exercise, LET me clarify my point so that you don’t get any more confused about data structures and algorithms or this series.

I’m sure there are some of you who are preparing for an interview, so you’ve heard about the interview building rocket, the job turning screw, and a lot of people have used this phrase to criticize the algorithmic interview of some of the biggest Internet companies today, so there is no use learning algorithms except for the interview.

I am not totally against this sentence, because now with the development of the ecological technology, you walk in the forefront in the field of Daniel have to rebuilt the wheels, general business problems directly take somebody else’s plan to use is ok, I also have seen in a word, just beginning to feel bullshit, think later feel so a truth:

Any technology that needs to cross a certain IQ threshold to master will not easily become popular.

In other words: technology becomes easier, more accessible, and more popular.

This is also true of current technology frameworks: simple enough to work, simple enough that you don’t need to know the complex details underneath.

So what’s your value as an intelligent and talented programmer?

In my opinion, the value depends on the problem you can solve. If you draw a simple Button according to the design draft, you can complete it, other front ends can also complete it, and even students at the back and back ends can almost complete the effect, then what about personal value? It just makes no difference what most people can easily do in a replaceable position.

But now if the face is a complex engineering problem, need you to develop a scaffolding tools, auxiliary business transformation framework source code to improve the extensibility of the project, or face severe performance problems immediately to analyze the reason, then gives the thinking of solving and balance in different elements, these are not an amateur player can do in a short time, This is where your value comes in.

Going back to the algorithm itself, it represents part of your ability to solve more complex problems.

It may not be easy to understand. Let’s take Vue as an example. If you have never been exposed to the concepts of depth-first traversal and recursion, and have not seen the corresponding code, you can hardly understand the source code of the entire patch of the virtual DOM. If you don’t have a systematic grasp of this feature, it’s hard to understand why you need to use the stack to check if the tag is closed properly during Vue template compilation. Similarly, if you don’t have code experience with backtracking, it is difficult to understand how the optimization phase of Vue template compilation checks for non-static child nodes and marks the parent nodes during depth-first traversal from parent to child. Also, if you didn’t know what the LRU cache elimination algorithm was, you might look at the keep-Alive implementation and wonder:

if (cache[key]) {
  vnode.componentInstance = cache[key].componentInstance
  // make current key freshest
  remove(keys, key)
  keys.push(key)
}
Copy the code

If the cache hit, why maintain an array of keys, and delete the key from the array, and put it at the end?

If you’ve had the basis of the algorithm before, you might think this is a very natural thing to do.

See? Do you think you can write great “star” projects without a solid foundation in data structures and algorithms?

Of course, it is not only the front end, I think the server side is also the same situation, here is not too many examples.

So folks, I think basic algorithmic ability is not a plus for an engineer who wants to solve complex problems, it’s a must. Algorithms are useful.

How to practice systematically?

I’m going to share some tips, or methods, for practicing data structures and algorithms, in two key words: systems and practices.

Special breakthrough

How to achieve systematic training?

I want to order according to the LeetCode one problem to brush is definitely not a problem system, mostly is the adjacent a few topic has no connection, this topic makes a list of related, the next question is a hash table, and then the next question and a binary search tree, thinking jump, on the one hand, may you very weak, the base of various data structures and algorithms to understand is not deep, Repeatedly jump to the place you are not familiar with, will frustrate your confidence, increase anxiety, and even direct to discourage, on the other hand, may meet a little more difficult list questions, you will not, you may wonder: is not just written out a list of questions? Why not now? It’s prone to self-doubt, which can also affect your drive to train.

Therefore, I think it is a relatively reasonable strategy to break through the training by topic. At the same time, it will make you master faster, so that it is easier to solve similar problems, enhance self-confidence.

Another thing to introduce is the thematic system of this series, which is divided into these modules:

This share is the linked list, stack and queue and binary tree part.

Deliberate practice

The book “Outliers: A Different Kind of Success Revelation” talks about the theory of 10,000 hours of deliberate practice to become a master, and a lot of people have talked about this theory since. I heard about it a few years ago, but it was in the process of training the algorithm that I really realized its practical significance, and it was after a lot of detours. You can see how hard it is to get from theory to practice.

My understanding of deliberate practice, when applied to the training of algorithms, is two points:

1. Often do problems you can’t do

2. A variety of solutions in turn to maximize the value of a problem

Deliberate practice An important point is to get out of your comfort zone. For practicing algorithm is the same, why a lot of people think brush algorithm is useless, it is because they are always doing their familiar topic, in their familiar way, squatting in their comfort zone, to do so is more significance is not big, but if you are always doing their unskilled topic, using different methods, is quite helpful for the growth of their own thinking, So I think to grasp the regular to do not do the problem, the more the better, of course, time is limited, we need to choose according to their own needs.

The reason I call this series exercises rather than brushes is because the essence of practice is practice, not just AC. Like this one:

And for those of you who have experience, it’s very easy to solve it recursively. But, have you thought about how to do it in a non-recursive way? If you can use non-recursion is to achieve once, I believe that the help and improvement will be much greater than the recursive solution.

By the way, all of the code in this series is original and not only presents recursive code, but also non-recursive solutions in the vast majority of cases, to get the most out of a problem and practice it rather than brushing it.

Is the last of the last, I want to emphasize: for the science of uniting the practice of internal work, no video or column is only auxiliary function, is the most important thing is their persistence and independent thinking, if you pass this series I can let oneself ability of algorithm to the next level, or something, you should thank you. If you think this series is good, I hope you can enter the GitHub address and give this project a star. Thank you very much!

List article

Reverse a linked list

Reverse linked list there are three questions for you to train on. Are the reverse of the single linked list in situ, two a group of reverse linked list and K a group of reverse linked list, the difficulty from the step up.

And in the interview whenever encountered a list, the frequency of the reverse class of questions is also one of the first or second, so it as a list of the opening training type, I hope we can cause enough attention 💪.

No.1 simple reverse linked list

Inverts a single linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

Source: LeetCode problem 206

Cyclic solution

This question is a classic topic in the list, fully reflect the list of data structure operation idea is simple, but the implementation is not so simple characteristics.

What should we pay attention to in the implementation?

Save subsequent nodes. As a beginner, it’s easy to point the next pointer of the current node directly to the previous node, but the pointer to the next node of the current node is lost. Therefore, you need to save the next node during the traversal, and then operate on the next point.

The linked list structure sound is defined as follows:

function ListNode(val) {
  this.val = val;
  this.next = null;
}
Copy the code

The implementation is as follows:

/** * @param {ListNode} head * @return {ListNode} */
let reverseList =  (head) = > {
    if(! head)return null;
    let pre = null, cur = head;
    while (cur) {
        // Key: save the value of the next node
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};
Copy the code

Because the logic is simple, the code is straightforward. But it’s not enough to just write it. For linked list problems, the custom of boundary checking can help us further ensure the quality of the code. To be specific:

• When the head node is empty, we have processed it, via ✅
• When the list contains onlyA nodeAt this point we want to return this node directly, in the case of the above code, after entering the looppreTo be an assignmentcur, that is,head, through ✅

Running in LeetCode, successful AC ✌

However, as a systematic training, it is too hasty to just let the program pass. We will try to solve the same problem in different ways in the future, so as to achieve a comprehensive effect. It is also a development of our own thinking, and sometimes we may reach a better solution.

Recursive solution

Since the previous idea has been very clear, so here we paste the code, you have a good experience:

let reverseList = (head) = >{
  let reverse = (pre, cur) = > {
    if(! cur)return pre;
    // Save the next node
    let next = cur.next;
    cur.next = pre;
    return reverse(cur, next);
  }
  return reverse(null, head);
}
Copy the code

No.2 interval reversal

Inverts the list from position m to n. Use one scan to complete the reversal.

Note: 1 ≤ M ≤ N ≤ Length of the list.

Example:

Input: 1 - > 2 - > 3 - > 4 - > 5 - > NULL, m = 2, n = 4 output: 1 - > > 4-3 - > 2 - > 5 - > NULLCopy the code

Problem 92

Train of thought

This problem compared to a whole list of reverse problems, in fact, the soup is not changed. We still have two types of solutions: cyclic solutions and recursive solutions.

The important thing to note is the preservation (or recording) of the front and back nodes. What does that mean? Look at this picture and you’ll see.

The definition of the front node and the back node, you should be able to see it more clearly on the graph, and we will use it a lot later.

The reverse operation has been dismantled in the last problem, so I won’t repeat it here. It should be noted that the work after the reversal is actually a grafting process for the whole interval after the reversal. First, the next of the former node points to the end of the interval, and then the next of the beginning of the interval points to the later node. Therefore, there are four nodes that need to be paid attention to in this problem: the front node, the back node, the interval starting point and the interval ending point. Now let’s get down to the actual coding.

Circulating solution

/** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} */
var reverseBetween = function(head, m, n) {
    let count = n - m;
    let p = dummyHead = new ListNode();
    let pre, cur, start, tail;
    p.next = head;
    for(let i = 0; i < m - 1; i ++) {
        p = p.next;
    }
    // Save the previous node
    front = p;
    // Save the first interval node at the same time
    pre = tail = p.next;
    cur = pre.next;
    // Interval reversal
    for(let i = 0; i < count; i++) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    // Next points to the end of the interval
    front.next = pre;
    // next of the first node of the interval points to the second node (cur after loop is the first node after the interval, i.e.
    tail.next = cur;
    return dummyHead.next;
};
Copy the code

The recursive method

The only difference with the recursive solution is that the interval is handled by a recursive program, and you can also review the implementation of recursive inversion.

var reverseBetween = function(head, m, n) {
  // Reverse the function recursively
  let reverse = (pre, cur) = > {
    if(! cur)return pre;
    // Save the next node
    let next = cur.next;
    cur.next = pre;
    return reverse(cur, next);
  }
  let p = dummyHead = new ListNode();
  dummyHead.next = head;
  let start, end; // The first and last nodes of the interval
  let front, tail; // Front node and back node
  for(let i = 0; i < m - 1; i++) {
    p = p.next;
  }
  front = p; // Save the previous node
  start = front.next;
  for(let i = m - 1; i < n; i++) {
    p = p.next;
  }
  end = p;
  tail = end.next; // Save the node
  end.next = null;
  // The front node points to the interval head, and the interval head points to the back node
  front.next = reverse(null, start);
  start.next = tail;
  return dummyHead.next;
}
Copy the code

No.3 Two sets of reverse lists

Given a linked list, swap the adjacent nodes in pairs and return the swapped list.

You can’t just change the values inside a node, but actually switch nodes.

Problem 24

Example:

Given 1->2->3->4, you should return 2->1->4->3.Copy the code

Train of thought

As shown in the figure, we first set up a virtual head node (dummyHead) to assist our analysis.

First, put p at dummyHead and record the nodes of p.ext and p.ext. Next, i.e. Node1 and node2.

Next = node2.next, effect:

Next = node1

Finally, dummyHead.next = node2, and the flip is complete. Meanwhile, the p pointer points to node1, and the effect is as follows:

If p.ext or p.ext. Next is null, no new set of nodes can be found, the loop ends.

Cycle to solve

The idea is clear, in fact, the implementation is relatively easy, the code is as follows:

var swapPairs = function(head) {
    if(head == null || head.next == null) 
        return head;
    let dummyHead = p = new ListNode();
    let node1, node2;
    dummyHead.next = head;
    while((node1 = p.next) && (node2 = p.next.next)) {
        node1.next = node2.next;
        node2.next = node1;
        p.next = node2;
        p = node1;
    }
    return dummyHead.next;
};
Copy the code

recursively

var swapPairs = function(head) {
    if(head == null || head.next == null)
        return head;
    let node1 = head, node2 = head.next;
    node1.next = swapPairs(node2.next);
    node2.next = node1;
    return node2;
};
Copy the code

Does the code feel very concise after using recursion? 😃 😃 😃

I hope you can have a good experience of the recursive invocation process, I believe that understanding will be a great improvement for yourself.

No.4 A group of K reverse linked list

I give you a list, and I flip it every k nodes, and I ask you to return the list.

K is a positive integer whose value is less than or equal to the length of the list.

If the total number of nodes is not an integer multiple of K, leave the last remaining nodes in their original order.

Example:

Given this list: 1 - > 2 - > 3 - > when k = 2, 4 - > 5, should return: 4 - > 2 - > 1 - > 3 - > 5 when k = 3, should return: 3 - > 2 - > 1 - > 4 - > 5Copy the code

Description:

• Your algorithm can only use constant extra space.
• You can’t just change the values inside a node, but actually switch nodes.

Problem 25

Train of thought

The idea is similar to No.3 in two a group of rollovers. The only difference is that in the case of two groups, each group only needs to reverse two nodes, while in the case of K groups, the corresponding operation is to reverse the list of K elements.

The recursive method

I think the recursive method is easier to understand, so let’s paste the recursive method code first.

The following code comments refer to the concepts’ first node ‘, ‘tail node’ and so on for the list before inversion.

/** * @param {ListNode} head * @param {number} k * @return {ListNode} */
var reverseKGroup = function(head, k) {
    let pre = null, cur = head;
    let p = head;
    // The following loop checks whether the following elements can form a group
    for(let i = 0; i < k; i++) {
        if(p == null) return head;
        p = p.next;
    }
    for(let i = 0; i < k; i++){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    // pre is the last node in the group and cur is the starting point for the next group
    head.next = reverseKGroup(cur, k);
    return pre;
};
Copy the code

Circulating solution

It’s all in the comments.

var reverseKGroup = function(head, k) {
    let count = 0;
    // See if you can form a group and count the number of elements
    for(letp = head; p ! =null; p = p.next) {
        if(p == null && i < k) return head;
        count++;
    }
    let loopCount = Math.floor(count / k);
    let p = dummyHead = new ListNode();
    dummyHead.next = head;
    // Divide into loopCount groups and reverse each group
    for(let i = 0; i < loopCount; i++) {
        let pre = null, cur = p.next;
        for(let j = 0; j < k; j++) {
            let next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // Currently pre is the end node of the group, and cur is the first node of the next group
        let start = p.next;// Start is the first node in the group
        // Start threading! The idea is exactly the same as in the two cases
        p.next = pre;
        start.next = cur;
        p = start;
    }
    return dummyHead.next;
};
Copy the code

Circular linked list

No.1 How to detect the link list forming a ring?

Given a linked list, determine whether a ring is formed in the list.

Train of thought

Idea 1: Loop once, use the Set data structure to save the node, use the memory address of the node to judge the weight, if the same node passed twice, it has formed a ring.

Train of thought 2: use the fast and slow pointer, the fast pointer takes two steps at a time, and the slow pointer takes one step at a time. If the two meet, it indicates that a loop has been formed.

Now, you might be wondering, why is idea two always meeting in a ring?

In fact, if there is a loop, both of them must go into the loop at the same time, so in the loop, take the slow pointer as the reference frame, and every time the fast pointer moves forward, it will eventually go back to the origin, which is the position of the slow pointer, so that the two meet. If there is no ring, then the two are further and further apart and never meet.

Now let’s do it programmatically.

Method 1: Set the severity

/** * @param {ListNode} head * @return {boolean} */
var hasCycle = (head) = > {
    let set = new Set(a);let p = head;
    while(p) {
        // If the same node is encountered again, there is a ring
        if(set.has(p)) return true;
        set.add(p);
        p = p.next;
    }
    return false;
}
Copy the code

Method two: fast pointer

var hasCycle = function(head) {
    let dummyHead = new ListNode();
    dummyHead.next = head;
    let fast = slow = dummyHead;
    // Zero nodes or one node, there must be no loop
    if(fast.next == null || fast.next.next == null) 
        return false;
    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        // The two met
        if(fast == slow) {
            return true; }}return false;
};
Copy the code

No.2 How to find the starting point of the loop

Given a linked list, return the first node where the list started to enter the loop. Null is returned if the list is loopless.

** Description: ** is not allowed to modify the given list.

Thought analysis

Now that we know how to tell if a ring is present, how do we find the nodes of the ring? Let’s analyze a wave.

This may seem trivial, but let’s abstract it further:

Let the fast and slow pointer go x seconds, and the slow pointer go once a second.

For the fast pointer, there is 2x -l = m * S + Y —–①

For the slow pointer, there is: x-l = n * S + Y —–②

Where, m and n are natural numbers.

① – ② * 2

L = (m-n) * s-y —–③

Ok, so this is a very important equation. We now assume that we have a new pointer at the leftmost end of segment L, and the slow Pointers are still at the meeting point.

Let the new pointer and the slow pointer take one step at a time, so when the new pointer takes L steps and reaches the starting point of the loop, meanwhile, let’s see what happens to the slow pointer.

According to formula ③, the slow pointer travels by (m-n) * s-y units, and the position when it meets is Y, taking the starting point of the ring as a reference. Now, from Y + (m-n) * s-y, that is, (m-n) * S, we know that the slow pointer actually travels a full (m-n) circle with reference to the starting point of the ring. In other words, the slow pointer now reaches the starting point of the loop. When the fast and slow Pointers meet, let the new pointer start from the beginning, and the slow pointer advance at the same time, and each step forward, where the two meet, is the starting point of the loop. : : :

Programming to realize

Once you understand the principle, it’s a lot easier to implement.

/** * @param {ListNode} head * @return {ListNode} */
var detectCycle = function(head) {
    let dummyHead = new ListNode();
    dummyHead.next = head;
    let fast = slow = dummyHead;
    // Zero nodes or one node, there must be no loop
    if(fast.next == null || fast.next.next == null) 
        return null;
    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        // The two met
        if(fast == slow) {
           let p = dummyHead;
           while(p ! = slow) { p = p.next; slow = slow.next; }returnp; }}return null;
};
Copy the code

List to merge

No.1 combines two ordered linked lists

Merge two ordered lists into a new ordered list and return. The new list is formed by concatenating all the nodes of the given two lists.

Example:

Input: 1->2->4; Output: 1->1->2->3->4->4Copy the code

Question 21

The recursive method

The recursive solution is easier to understand, so let’s do it recursively:

/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */
var mergeTwoLists = function(l1, l2) {
    const merge = (l1, l2) = > {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val > l2.val) {
            l2.next = merge(l1, l2.next);
            return l2;
        }else {
            l1.next = merge(l1.next, l2);
            returnl1; }}return merge(l1, l2);
};
Copy the code

Circulating solution

var mergeTwoLists = function(l1, l2) {
    if(l1 == null) return l2;
    if(l2 == null) return l1;
    let p = dummyHead = new ListNode();
    let p1 = l1, p2 = l2;
    while(p1 && p2) {
        if(p1.val > p2.val) {
            p.next = p2;
            p = p.next;
            p2 = p2.next;
        }else{ p.next = p1; p = p.next; p1 = p1.next; }}// Be sure to check the rest of the loop once it is complete
    if(p1) p.next = p1;
    else p.next = p2;
    return dummyHead.next;
};
Copy the code

Merge K ordered linked lists

Merge k sorted lists and return the merged sorted list. Analyze and describe the complexity of the algorithm.

Example:

Input: [1 - > 4 - > 5, 1 - > 3 - > 4, 2 - > 6] output: 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

Question 23

Top-down (recursive) implementation

/** * @param {ListNode[]} lists * @return {ListNode} */
var mergeKLists = function(lists) {
    // The above is already implemented
    var mergeTwoLists = function(l1, l2) {/* * * has been implemented above};
    const _mergeLists = (lists, start, end) = > {
        if(end - start < 0) return null;
        if(end - start == 0)return lists[end];
        let mid = Math.floor(start + (end - start) / 2);
        return mergeTwoList(_mergeLists(lists, start, mid), _mergeLists(lists, mid + 1, end));
    }
    return _mergeLists(lists, 0, lists.length - 1);
};
Copy the code

Bottom-up implementation

I want to remind you that in the bottom-up implementation, I bound a dummyHead pointer (dummyHead) to each linked list. Why did I do that?

For example, after l1 and L2 are merged, the head pointer of the merged list is directly l1 dummyhead. next, which means that both lists are merged into L1, which facilitates the subsequent merge operation.

var mergeKLists = function(lists) {
    var mergeTwoLists = function(l1, l2) {/* * * has been implemented above};
    // Boundary case
    if(! lists || ! lists.length)return null;
    // Set of virtual header Pointers
    let dummyHeads = [];
    // Initialize the virtual header pointer
    for(let i = 0; i < lists.length; i++) {
        let node = new ListNode();
        node.next = lists[i];
        dummyHeads[i] = node;
    }
    // Merge from the bottom up
    for(let size = 1; size < lists.length; size += size){
        for(let i = 0; i + size < lists.length; i +=2* size) { dummyHeads[i].next = mergeTwoLists(dummyHeads[i].next, dummyHeads[i + size].next); }}return dummyHeads[0].next;
};
Copy the code

Multiple list merge here to complete the implementation, here by the way to tell you the way this merge is also the core code for the list merge sort. I hope you can have a good experience of top-down and bottom-up two different implementation details, I believe to your programming skills is a good improvement.

Find the middle node of the list

Determine palindrome lists

Please determine whether a single linked list is a palindrome list.

Example 1:

Input: 1->2 Output:false
Copy the code

Example 2:

Input: 1->2->2->1true
Copy the code

Can you solve this problem with O(n) time and O(1) space?

Question 234

Thought analysis

This is a fairly simple problem, if you ignore the performance constraints. But given the complexity of O(n) time and O(1) space, it’s worth stopping and thinking.

There is no way to access the previous nodes, so we have to do something else:

Find the midpoint of the list, and then reverse the latter half, you can compare and draw a conclusion. So let’s do a wave.

Code implementation

In fact, the key part of the code is to find the midpoint. Strong-arm reaction first:

  let dummyHead = slow = fast = new ListNode();
  dummyHead.next = head;
  // Look, it's time to find the middle point
  while(fast && fast.next) {
      slow = slow.next;
      fast = fast.next.next;
  }
Copy the code

And you might be wondering, why is the boundary set like this?

Let’s think about it for an odd number of nodes and an even number of nodes.

• When the number of linked list nodes is odd

Try to simulate, when FAST is empty, stop the loop, the state is as follows:

• When the number of linked list nodes is even

For the two conditions, in the case of odd numbers, fast is always empty first, and in the case of even numbers, fast. Next always appears first.

That is to say: once fast is empty, the number of linked list nodes must be odd, otherwise it is even. Therefore, the two cases can be combined to discuss, when fast is empty or fast. Next is empty, the loop can be terminated.

The full implementation is as follows:

/** * @param {ListNode} head * @return {boolean} */
var isPalindrome = function(head) {
    let reverse = (pre, cur) = > {
        if(! cur)return pre;
        let next = cur.next;
        cur.next = pre;
        return reverse(cur, next);
    }
    let dummyHead = slow = fast = new ListNode();
    dummyHead.next = head;
    // Look for the middle point, gold template
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let next = slow.next;
    slow.next = null;
    let newStart = reverse(null, next);
    for(letp = head, newP = newStart; newP ! =null; p = p.next, newP = newP.next) {
        if(p.val ! = newP.val)return false;
    }
    return true;
};
Copy the code

Stack and queue pieces

Stack & recursion

Effective brackets

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, determine whether the string is valid.

A valid string must meet the following requirements:

The opening parenthesis must be closed with a closing parenthesis of the same type. The opening brackets must be closed in the correct order. Note that an empty string can be considered a valid string.

Example:

Input:"()"Output:true
Copy the code

Question 20

Code implementation

/** * @param {string} s * @return {boolean} */
var isValid = function(s) {
    let stack = [];
    for(let i = 0; i < s.length; i++) {
        let ch = s.charAt(i);
        if(ch == '(' || ch == '[' || ch == '{') 
            stack.push(ch);
        if(! stack.length)return false;
        if(ch == ') '&& stack.pop() ! = ='(') return false;
        if(ch == '] '&& stack.pop() ! = ='[' ) return false;
        if(ch == '} '&& stack.pop() ! = ='{') return false;
    }
    return stack.length === 0;
};
Copy the code

Multidimensional array flatten

Convert a multidimensional array to a one-dimensional array.

Example:

[1, [2, [3, [4, 5]], 6] -> [1, 2, 3, 4, 5, 6]Copy the code

Code implementation

/** * @constructor * @param {NestedInteger[]} nestedList * @return {Integer[]} */
let flatten = (nestedList) = > {
    let result = [];
    let fn = function (target, ary) {
        for (let i = 0; i < ary.length; i++) {
            let item = ary[i];
            if (Array.isArray(ary[i])) {
                fn(target, item);
            } else {
                target.push(item);
            }
        }
    }
    fn(result, nestedList)
    return result;

Copy the code

At the same time, the reduce method can be used to solve the problem in one row, which is very concise.

let flatten = (nestedList) = >  nestedList.reduce((pre, cur) = > pre.concat(Array.isArray(cur) ? flatten(cur): cur), [])
Copy the code

Binary tree sequence traversal

The sequence traversal of binary trees is for the next chapter, but the nature of queues is too obvious, so this kind of problem is used to practice the operation of queues. This will not only involve ordinary sequence traversal, but also deformation, so that you can understand it thoroughly.

Normal level traversal

Given a binary tree, return the values of the nodes traversed hierarchically. (that is, access all nodes layer by layer, from left to right).

Example:

  3
  / \
9  20
  /  \
  15   7
Copy the code

The result should be output:

[[3], [9,20], [15,7]Copy the code

Source: LeetCode question 102

implementation

/** * @param {TreeNode} root * @return {number[][]} */
var levelOrder = function(root) {
    if(! root)return [];
    let queue = [];
    let res = [];
    let level = 0;
    queue.push(root);
    let temp;
    while(queue.length) {
        res.push([]);
        let size = queue.length;
        // Note: size -- is a very important technique in hierarchy traversal
        while(size --) {
            / / out of the team
            let front = queue.shift();
            res[level].push(front.val);
            / / team
            if(front.left) queue.push(front.left);
            if(front.right) queue.push(front.right);
        }        
        level++;
    }
    return res;
};
Copy the code

Zigzag hierarchical traversal of binary trees

Given a binary tree, return a zigzag hierarchical traversal of its node values. (that is, first from left to right, then from right to left to the next layer, and so on, alternating between layers).

Such as:

Given a binary tree [3,9,20,null,null,15,7], the output should look like this:

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Return zigzag hierarchy traversal as follows:

[[3],
  [20.9],
  [15.7]]Copy the code

Question 103

Train of thought

This is a slightly different idea, but if you get the idea of hierarchical traversal, it’s pretty easy.

Code implementation

var zigzagLevelOrder = function(root) { if(! root) return []; let queue = []; let res = []; let level = 0; queue.push(root); let temp; while(queue.length) { res.push([]); let size = queue.length; While (size --) {let front = queue.shift(); res[level].push(front.val); if(front.left) queue.push(front.left); if(front.right) queue.push(front.right); } if(level % 2) res[level].reverse(); level++; } return res; };Copy the code

Right view of the binary tree

Given a binary tree, imagine yourself standing on the right side of it and return the values of the nodes visible from the right, in order from top to bottom.

Example:

Input: [5, 1, 2, 3, null, null, 4] output: [1, 3, 4] explanation: < 1-2 3 < / \ - \ \ 5 4 < -- -- -Copy the code

Source: LeetCode problem 199

Train of thought

Right view? If you think of it in terms of DFS, or depth-first search, it’s incredibly painful. Yeah, that’s how I got ripped off 🙂

But if you use the breadth-first search idea, that is, in order to traverse the way, it is easy to solve this problem.

Code implementation

/** * @param {TreeNode} root * @return {number[]} */
var rightSideView = function(root) {
    if(! root)return [];
    let queue = [];
    let res = [];
    queue.push(root);
    while(queue.length) {
        res.push(queue[0].val);
        let size = queue.length;
        while(size --) {
            // A loop of size is a loop of one level, where only the rightmost node is taken
            let front = queue.shift();
            if(front.right) queue.push(front.right);
            if(front.left) queue.push(front.left); }}return res;
};
Copy the code

Diagram BFS traversal is not authorized

Perfect square

Given a positive integer n, find several perfect squares (e.g., 1, 4, 9, 16…). So that their sum is equal to n. You need to minimize the number of perfect squares that make up the sum.

Example:

Input: n = 12 Output: 3 Description: 12 = 4 + 4 + 4.Copy the code

Question 279

Train of thought

The easiest way to think about this is dynamic programming, and we’ll break it down later. In fact, using queues to model graphs can also be solved smoothly with breadth-first traversal.

You might be a little confused by this picture, but let me explain it a little bit.

In this graph of non-entitlements, each point points to the last node it might have passed through. For example, for 5, it could be the conversion of 4 plus 1 squared, or it could be the conversion of 1 plus 2 squared, so it’s related to both 1 and 2, and so on.

So what we’re going to do now is find the shortest number of lines to go from n to 0.

For example, when n = 8, we need to find its neighbor nodes 4 and 7. At this time, the number of steps to reach 4 and 7 is 1. Then, starting from 4 and 7, 4 finds neighbor nodes 3 and 0, and the number of steps to reach 3 and 0 is 2. Return the number of steps to 0 of 2.

Talk is cheap, show me your code. Let’s take a step by step approach to this search.

implementation

Let’s implement the first version of the code.

/** * @param {number} n * @return {number} */
var numSquares = function(n) {
    let queue = [];
    queue.push([n, 0]);
    while(queue.length) {
        let [num, step] = queue.shift();
        for(let i = 1; ; i ++) {
            let nextNum = num - i * i;
            if(nextNum < 0) break;
            // Return step + 1 for the last step
            if(nextNum == 0) return step + 1;
            queue.push([nextNum, step + 1]); }}// There is no need to return another value, because 1 is also a perfect square, and all numbers can be combined with 1
};
Copy the code

This solution is functionally fine, but it hides a huge performance problem that you can test with LeetCode, basically timeouts.

So why is this a problem?

It comes out in this line of code:

queue.push([nextNum, step + 1]);
Copy the code

Anything greater than 0, I’m going to put in the queue. 2-1 = 1, 5-4 = 1, 9-8 = 1…… It’s going to repeat a lot of 1’s, and so on, and so on, and so on, and so on.

This large number of repeated numbers not only consumes more loop times, but also puts more pressure on memory space.

Therefore, we need to mark the numbers that have been pushed into the queue to avoid repeated pushing. The improved code is as follows:

var numSquares = function(n) {
    let map = new Map(a);let queue = [];
    queue.push([n, 0]);
    map.set(n, true);
    while(queue.length) {
        let [num, step] = queue.shift();
        for(let i = 1; ; i++) {
            let nextNum = num - i * i;
            if(nextNum < 0) break;
            if(nextNum == 0) return step + 1;
            // nextNum has not been accessed
            if(! map.get(nextNum)){ queue.push([nextNum, step +1]);
                // The tag has already been accessed
                map.set(nextNum, true); }}}};Copy the code

randomly

Given two words (beginWord and endWord) and a dictionary, find the length of the shortest conversion sequence from beginWord to endWord. The conversion must follow the following rules:

• Only one letter can be changed per conversion.
• The intermediate word in the transformation must be a dictionary word.

Description:

1. If no such sequence of transformations exists, return 0.
2. All words have the same length.
3. All words consist of lowercase letters only.
4. There are no duplicate words in the dictionary.
5. You can assume that beginWord and endWord are non-empty and that they are not the same.

Example:

Enter beginWord ="hit",
endWord = "cog",
wordList = ["hot"."dot"."dog"."lot"."log"."cog"[Output: 5 Explanation: a shortest transformation sequence is"hit" -> "hot" -> "dot" -> "dog" -> "cog"Returns its length 5.Copy the code

Problem 127

Train of thought

This is one of the more typical graphically modeled problems. If each word is a node, it is a neighboring node as long as it is different from the word by only one letter.

Here we can do the traversal by means of BFS. The implementation is as follows:

Code implementation

/** * @param {string} beginWord * @param {string} endWord * @param {string[]} wordList * @return {number} */
var ladderLength = function(beginWord, endWord, wordList) {
    // Whether two words are adjacent in the diagram
    const isSimilar = (a, b) = > {
        let diff = 0
        for(let i = 0; i < a.length; i++) {
            if(a.charAt(i) ! == b.charAt(i)) diff++;if(diff > 1) return false; 
        }
        return true;
    }
    let queue = [beginWord];
    let index = wordList.indexOf(beginWord);
    if(index ! = =- 1) wordList.splice(index, 1);
    let res = 2;
    while(queue.length) {
        let size = queue.length;
        while(size --) {
            let front = queue.shift();
            for(let i = 0; i < wordList.length; i++) {
                if(! isSimilar(front, wordList[i]))continue;
                / / found
                if(wordList[i] === endWord) {
                    return res;
                }
                else {
                    queue.push(wordList[i]);
                }
                WordList [I] = wordList[I] = wordList[I
                // This step is critical for performance optimization, otherwise 100% time out
                wordList.splice(i, 1); i --; }}Steps / / + 1
        res += 1;
    }
    return 0;
};
Copy the code

Implementing a priority queue

A priority queue is a special type of queue whose bottom layer uses the structure of the heap so that the first element of the queue is always the highest priority each time it is added or removed. It is up to us to decide what fields to prioritize and how to compare them.

To implement a priority queue, first implement a heap structure.

A note about the heap

You may not have seen a heap before, but it’s a very simple structure. It’s essentially a binary tree. But the binary tree is more special, in addition to use an array to store in turn each node (the node corresponding to the array subscript and sequence traversal sequence number), it need to make sure that any child more priority than a parent node, it is also its most critical nature, because to ensure the root element must be the highest priority.

Here’s an example:

Now the array of the heap is: [10, 7, 2, 5, 1]

This results in two very critical operations – siftUp and siftDown.

For the siftUp operation, if you have a normal heap, where any parent element has a higher priority than the child element, and you add another element to the end of the heap array, you might not fit the structure of the heap. So now I compare the newly added node to its parent, and if the parent has a lower priority than it, then the two are switched up and up to the root node, thus ensuring the correct structure of the heap. And that operation is called siftUp.

SiftDown is an operation in the opposite direction, from top to bottom, the same principle, also to ensure the correct structure of the heap.

Implement a maximum heap

The maximum heap, or the element at the top of the heap, is the element with the highest priority.

// Use the maximum heap example to implement a wave
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
class MaxHeap {
  constructor(arr = [], compare = null) {
    this.data = arr;
    this.size = arr.length;
    this.compare = compare;
  }
  getSize() {
    return this.size;
  }
  isEmpty() {
    return this.size === 0;
  }
  // Add the element
  add(value) {
    this.data.push(value);
    this.size++;
    // siftUp the added element
    this._siftUp(this.getSize() - 1);
  }
  // Find the highest priority element
  findMax() {
    if (this.getSize() === 0)
      return;
    return this.data[0];
  }
  // Let the element with the highest priority (that is, the first element) out of the queue
  extractMax() {
    // 1. Save the first element of the queue
    let ret = this.findMax();
    // 2. Switch the first and last elements
    this._swap(0.this.getSize() - 1);
    // 3. Kick out the end of the queue
    this.data.pop();
    this.size--;
    // 4. New team leader siftDown
    this._siftDown(0);
    return ret;
  }

  toString() {
    console.log(this.data);
  }
  _swap(i, j) {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }
  _parent(index) {
    return Math.floor((index - 1) / 2);
  }
  _leftChild(index) {
    return 2 * index + 1;
  }
  _rightChild(index) {
    return 2 * index + 2;
  }
  _siftUp(k) {
    // Float up, as long as the child has a higher priority than the parent, the parent switches positions, all the way up to the root node
    while (k > 0 && this.compare(this.data[k], this.data[this._parent(k)])) {
      this._swap(k, this._parent(k));
      k = this._parent(k);
    }
  }
  _siftDown(k) {
    // There is a left child
    while (this._leftChild(k) < this.size) {
      let j = this._leftChild(k);
      // There is a right child and the right child is older than the left child
      if (this._rightChild(k) < this.size &&
        this.compare(this.data[this._rightChild(k)], this.data[j])) {
        j++;
      }
      if (this.compare(this.data[k], this.data[j]))
        return;
      // The parent node is smaller than the child node
      this._swap(k, j);
      // Continue sinkingk = j; }}}Copy the code

Implementing a priority queue

With the maximum heap in place, implementing a priority queue is a piece of cake. No more nonsense, just put the code in.

class PriorityQueue {
  // Max indicates the capacity of the priority queue
  constructor(max, compare) {
    this.max = max;
    this.compare = compare;
    this.maxHeap = new MaxHeap([], compare);
  }

  getSize() {
    return this.maxHeap.getSize();
  }

  isEmpty() {
    return this.maxHeap.isEmpty();
  }

  getFront() {
    return this.maxHeap.findMax();
  }

  enqueue(e) {
    // If it is higher than the current highest priority, it is not dealt with directly
    if (this.getSize() === this.max) {
      if (this.compare(e, this.getFront())) return;
      this.dequeue();
    }
    return this.maxHeap.add(e);
  }

  dequeue() {
    if (this.getSize() === 0) return null;
    return this.maxHeap.extractMax(); }}Copy the code

So, isn’t that easy? So much for the fabled priority queue.

Hold on, one might ask: how do you ensure that this priority queue is correct?

Let’s take a test:

let pq = new PriorityQueue(3);
pq.enqueue(1);
pq.enqueue(333);
console.log(pq.dequeue());
console.log(pq.dequeue());
pq.enqueue(3);
pq.enqueue(6);
pq.enqueue(62);
console.log(pq.dequeue());
console.log(pq.dequeue());
console.log(pq.dequeue());
Copy the code

Here are the results:

333, 1, 62, 6, 3Copy the code

As you can see, the function of this priority queue meets our expectations. Later, we will use this data structure to solve the problem through practical examples.

Priority queue application

The first K high frequency elements

Given a non-empty array of integers, return the elements that occur k above the frequency of occurrence.

Example:

Input: nums = [1,1,1,2, 3], k = 2 output: [1,2]Copy the code

Description:

• You can assume that the given k is always reasonable and that 1 is less than or equal to k is less than or equal to the number of different elements in the array.
• Your algorithm has to be better than order n log n, where n is the size of the array.

Source: LeetCode question 347

Train of thought

The first thing you have to do is count the frequency, and then how do you pick the first K elements of the frequency that are less than order n log n?

And, of course, this is a typical example of looking at a priority queue, where you take a priority queue of capacity K and every time you kick out something that doesn’t meet the criteria, what’s left is what you get. The whole time becomes order n log K, which is obviously less than order n log n.

Since it is a priority queue, it involves how to define the priority.

If we take the high frequency as the high priority, then the first element of the queue is always the high frequency element, so every time we leave the queue, we will kick out the element with the highest frequency. If we assume that the priority queue size is K, then we will leave the K elements with the lowest frequency.

So, what we need to do is kick out the lowest frequency element every time we get out of the team, so that we’re left with the highest frequency K elements.

Should we rewrite the implementation of a small top heap in order to kick out the least frequent elements?

Absolutely not! As I said earlier, the comparative logic of the priorities can be reasonably defined. So let’s do that.

Code implementation

var topKFrequent = function(nums, k) {
   let map = {};
   let pq = new PriorityQueue(k, (a, b) => map[a] - map[b] < 0);
   for(let i = 0; i < nums.length; i++) {
       if(! map[nums[i]]) map[nums[i]] =1;
       else map[nums[i]] = map[[nums[i]]] + 1;
   }
   let arr = Array.from(new Set(nums));
   for(let i = 0; i < arr.length; i++) {
       pq.enqueue(arr[i]);
   }
   return pq.maxHeap.data;
};
Copy the code

Merge K sorted lists

Merge k sorted lists and return the merged sorted list. Analyze and describe the complexity of the algorithm.

Example:

Input: [1 - > 4 - > 5, 1 - > 3 - > 4, 2 - > 6] output: 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

This problem we have previously implemented in the linked list section, but it can also be solved perfectly with priority queues.

Question 23

/** * @param {ListNode[]} lists * @return {ListNode} */
var mergeKLists = function(lists) {
    let dummyHead = p = new ListNode();
    // Define priority function, important!
    let pq = new PriorityQueue(lists.length, (a, b) => a.val <= b.val);
    // Push the header into the priority queue
    for(let i = 0; i < lists.length; i++) 
        if(lists[i]) pq.enqueue(lists[i]);
    // Fetch the node with the smallest value. If next is not empty, push the node into the queue
    while(pq.getSize()) {
        let min = pq.dequeue();
        p.next = min;
        p = p.next;
        if(min.next) pq.enqueue(min.next);
    }
    return dummyHead.next;
};
Copy the code

How about that? Wow! Originally the priority queue can be used like this!

Dual-end queues and applications

What is a two-enqueued?

A double-endian queue is a special type of queue. Elements can be added or removed at the beginning and end of the queue. It is a kind of enhanced queue.

JS array is a typical double-ended queue. The push and pop methods add and remove elements from the tail, and the unshift and shift methods add and remove elements from the head, respectively.

Maximum sliding window

Given an array nums, a sliding window of size k moves from the leftmost part of the array to the rightmost part of the array. You can only see k numbers in the sliding window. Slide the window one bit to the right at a time.

Returns the maximum value in the sliding window.

Example:

Input: nums = [1, 3, 1, 3,5,3,6,7], and k = 3 output:,3,5,5,6,7 [3] : The position of the sliding window Maximum -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- [1] 3-1-3 3 5 6 7 3 1 [3-1-3] 3 5 6 7 3 1 3 [1-3-5] 3 6 7 5 3-1/3-3 5 6 7 5, 1, 3, 1, 5, 5, 6, 7, 6, 1, 3, 1, 5, 6, 7, 7Copy the code

Requirement: Time complexity should be linear.

Source: LeetCode problem 239

Train of thought

This is a problem that is typically solved using a two-ended queue.

Create a double-enqueued window. Each time a new value is pushed, all values smaller than it are currently in the window. Using the characteristics of the dual-end queue, you can iterate from the back to the front, and delete the small ones, otherwise stop.

This ensures that the top of the queue is always the maximum, so the time complexity of finding the maximum can be reduced to O(1). The overall time complexity is linear as more and more values in the window become obsolete.

Code implementation

The code is very concise, but if you want to write the bug free code is still quite difficult, hope you can achieve it by yourself.

var maxSlidingWindow = function(nums, k) {
    // Exception handling
    if(nums.length === 0| |! k)return [];
    let window = [], res = [];
    for(let i = 0; i < nums.length; i++) {
        // First, kick out the ones outside the sliding window
        if(window[0]! = =undefined && window[0] <= i - k) window.shift();
        // Make sure the team leader is the largest
        while(nums[window[window.length - 1]] <= nums[i])  window.pop();
        window.push(i);
        if(i >= k - 1) res.push(nums[window[0]])}return res;
};
Copy the code

Stack and queue implementations

Stack implementation queue

Use stacks to implement the following operations for queues:

Push (x) — To put an element at the end of the queue. Pop () — Removes an element from the head of the queue. Peek () – Returns the element at the head of the queue. Empty () — returns whether the queue is empty.

Example:

let queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  / / returns 1
queue.pop();   / / returns 1
queue.empty(); / / returns false
Copy the code

Problem 232

Train of thought

Since the stack is first in last out, to get the first in first out effect, we might as well use two stacks.

When we do push, we push to Stack1, and when we do pop and peek, we go through Stack2.

Of course, there is a special case, stack2 is empty, how to do pop and peek? Simply pop the elements in Stack1 and push them into Stack2, and then operate stack2 normally, as shown in the figure below:

This will ensure that it is first in, first out.

Code implementation

var MyQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};
// Move elements from Stack1 to Stack2
MyQueue.prototype.transform = function() {
  while(this.stack1.length) {
    this.stack2.push(this.stack1.pop());
  }
}

MyQueue.prototype.pop = function() {
  if(!this.stack2.length) this.transform();
  return this.stack2.pop();
};

MyQueue.prototype.peek = function() {
    if(!this.stack2.length) this.transform();
    return this.stack2[this.stack2.length - 1];
};

MyQueue.prototype.empty = function() {
    return !this.stack1.length && !this.stack2.length;
};
Copy the code

Queue implementation stack

Just the opposite of what we did in the last problem, we did it in a first-in, first-out format.

Train of thought

In the example of the queue above, push can be done directly from the end of the queue. But what about Pop and Peek?

So going back to our goal, our goal is to get the value at the end of the line, which is 3. So that’s easy to do, let’s get all the elements out of the queue, let’s just keep the elements at the end of the queue, and let’s put the rest of the elements in another queue.

Source: LeetCode Problem 225

Code implementation

During implementation, it’s worth noting that QueuE1 always holds the first element, and QueuE2 always holds the last element (that is, the top element on the stack).

But there is a catch when pushing. You cannot push the new value to queue1 when queue2 already has an element, because the top element should be updated. At this point, the new value should be pushed to Queue2, and then the old top of the stack should be pushed from QueuE2 to QueuE1, thus implementing the operation of updating the top of the stack.

var MyStack = function() {
    this.queue1 = [];
    this.queue2 = [];
};
MyStack.prototype.push = function(x) {
    if(!this.queue2.length) this.queue1.push(x);
    else {
        // Queue2 already has a value
        this.queue2.push(x);
        // The old stack top is moved to queue1
        this.queue1.push(this.queue2.shift()); }}; MyStack.prototype.transform =function() {
    while(this.queue1.length ! = =1) {
        this.queue2.push(this.queue1.shift())
    }
    // Queue2 holds the previous element
    // Switch queue1 and Queue2
    // Now queue1 contains the first elements, and queue2 contains only the last elements
    let tmp = this.queue1;
    this.queue1 = this.queue2;
    this.queue2 = tmp;
}
MyStack.prototype.pop = function() {
    if(!this.queue2.length) this.transform();
    return this.queue2.shift();
};
MyStack.prototype.top = function() {
    if(!this.queue2.length) this.transform();
    return this.queue2[0];
};
MyStack.prototype.empty = function() {
    return !this.queue1.length && !this.queue2.length;
};
Copy the code

Binary tree

Traversal of a binary tree

The former sequence traversal

Example:

Example: Input: [1, NULL,2,3] 1\2/3 Output: [1,2,3]Copy the code

Source: LeetCode question 144

recursively

/** * @param {TreeNode} root * @return {number[]} */
var preorderTraversal = function(root) {
    let arr = [];
    let traverse = (root) = > {
      if(root == null) return;
      arr.push(root.val);
      traverse(root.left);
      traverse(root.right); 
    }
    traverse(root);
    return arr;
};
Copy the code

Non-recursive

var preorderTraversal = function(root) {
    if(root == null) return [];
    let stack = [], res = [];
    stack.push(root);
    while(stack.length) {
        let node = stack.pop();
        res.push(node.val);
        // The left child is last in, first out, and the depth first traversal is left, then right
        if(node.right) stack.push(node.right);
        if(node.left) stack.push(node.left);
    }
    return res;
};
Copy the code

In the sequence traversal

Given a binary tree, return the in-order traversal of it.

Example:

Input: [1, NULL,2,3] 1\2/3 Output: [1,3,2]Copy the code

Question 94

Recursion:

/** * @param {TreeNode} root * @return {number[]} */
var inorderTraversal = function(root) {
    let arr = [];
    let traverse = (root) = > {
      if(root == null) return;
      traverse(root.left);
      arr.push(root.val);
      traverse(root.right); 
    }
    traverse(root);
    return arr;
};
Copy the code

Non-recursive

var inorderTraversal = function(root) {
    if(root == null) return [];
    let stack = [], res = [];
    let p = root;
    while(stack.length || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }
        let node = stack.pop();
        res.push(node.val);
        p = node.right;
    }   
    return res;
};
Copy the code

After the sequence traversal

Given a binary tree, return a sequential traversal of it.

Example:

Input: [1, NULL,2,3] 1\2/3 Output: [3,2,1]Copy the code

Problem 145

recursively

/** * @param {TreeNode} root * @return {number[]} */
var postorderTraversal = function(root) {
    let arr = [];
    let traverse = (root) = > {
      if(root == null) return;
      traverse(root.left);
      traverse(root.right);
      arr.push(root.val);
    }
    traverse(root);
    return arr
};
Copy the code

Non-recursive

var postorderTraversal = function(root) {
    if(root == null) return [];
    let stack = [], res = [];
    let visited = new Set(a);let p = root;
    while(stack.length || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }
        let node = stack[stack.length - 1];
        // If the right child exists and the right child has not been accessed
        if(node.right && ! visited.has(node.right)) { p = node.right; visited.add(node.right); }else{ res.push(node.val); stack.pop(); }}return res;
};
Copy the code

Maximum/minimum depth

Maximum depth

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: A leaf node is a node with no child nodes.

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

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its maximum depth of 3. Source: LeetCode Problem 104

The recursive implementation

The implementation is very simple, just post the code:

/** * @param {TreeNode} root * @return {number} */
var maxDepth = function(root) {
    // Recursive termination condition
    if(root == null) return 0;
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
};
Copy the code

Non-recursive implementation

It’s very easy to understand the sequence traversal.

var maxDepth = function(root) {
    if(root == null) return 0;
    let queue = [root];
    let level = 0;
    while(queue.length) {
        let size = queue.length;
        while(size --) {
            let front = queue.shift();
            if(front.left) queue.push(front.left);
            if(front.right) queue.push(front.right);
        }
        // The value after level ++ indicates how many layers of nodes have been processed
        level ++;
    }
    return level;
};
Copy the code

The minimum depth

Given a binary tree, find its minimum depth.

Minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node.

Note: A leaf node is a node with no child nodes.

Example:

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

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Return its minimum depth of 2.

Question 111

The recursive implementation

In the process of implementation, there is a pitfall if you follow the maximum depth approach, namely:

/** * @param {TreeNode} root * @return {number} */
var minDepth = function(root) {
    // Recursive termination condition
    if(root == null) return 0;
    return Math.min(minDepth(root.left) + 1, minDepth(root.right)+1);
};
Copy the code

When the root node has an empty child, it returns 1, but this is incorrect. The minimum height refers to the smallest path from the root node to the nearest leaf node, not to an empty node.

Therefore, we need to make the following adjustments:

var minDepth = function(root) {
    if(root == null) return 0;
    // If the left and right children are not empty, call it like this
    if(root.left && root.right)
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    // The right child is empty, ignore it directly
    else if(root.left)
        return minDepth(root.left) + 1;
    // Left child is empty, ignore
    else if(root.right)
        return minDepth(root.right) + 1;
    // If both children are empty, the leaf node is reached. Return 1
    else return 1;
};
Copy the code

Then the program will work.

Non-recursive implementation

Similar to the maximum height problem, the sequential traversal method is adopted, which is easy to understand.

var minDepth = function(root) {
    if(root == null) return 0;
    let queue = [root];
    let level = 0;
    while(queue.length) {
        let size = queue.length;
        while(size --) {
            let front = queue.shift();
            // Find the leaf node
            if(! front.left && ! front.right)return level + 1;
            if(front.left) queue.push(front.left);
            if(front.right) queue.push(front.right);
        }
        // The value after level ++ indicates how many layers of nodes have been processed
        level ++;
    }
    return level;
};
Copy the code

Symmetric binary tree

Given a binary tree, check whether it is mirror symmetric.

For example, a binary tree [1,2,2,3,4,4,3] is symmetric.

    1
   / \
  2   2
 / \ / \
3  4 4  3
Copy the code

But the following [1,2,2,null,3,null,3] is not mirror symmetric:

1 / \ 2 2\3 3Copy the code

Source: LeetCode 101

The recursive implementation

Recursion code is very dry and elegant, hope you first implement it yourself, and then compare and improve.

/** * @param {TreeNode} root * @return {boolean} */
var isSymmetric = function(root) {
    let help = (node1, node2) = > {
        / / is empty
        if(! node1 && ! node2)return true;
        // One is null and the other is not null, or the values of the two nodes are not equal
        if(! node1 || ! node2 || node1.val ! == node2.val)return false;
        return help(node1.left, node2.right) && help(node1.right, node2.left);
    }
    if(root == null) return true;
    return help(root.left, root.right);
};
Copy the code

Non-recursive implementation

A queue is used to save the visited nodes, and two nodes are retrieved at a time for comparison.

var isSymmetric = function(root) {
    if(root == null) return true;
    let queue = [root.left, root.right];
    let node1, node2;
    while(queue.length) {
        node1 = queue.shift();
        node2 = queue.shift();
        // Both nodes are empty
        if(! node1 && ! node2)continue;
        // One is null and the other is not null, or the values of the two nodes are not equal
        if(! node1 || ! node2 || node1.val ! == node2.val)return false;
        queue.push(node1.left);
        queue.push(node2.right);
        queue.push(node1.right);
        queue.push(node2.left);
    }
    return true;
};
Copy the code

LCA problem

Inflationary Common Ancestor (LCA)

The definition of recent public ancestor in Baidu Encyclopedia is: “For two nodes P and Q of the root tree T, the recent public ancestor is expressed as a node X, where x is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

The nearest common ancestor of a binary tree

For a simple binary tree: root = [3,5,1,6,2,0,8, null, null, 7, 4]

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, output q = 1:3: node 5 and 1 recent common ancestor node 3.Copy the code

Source: LeetCode Problem 236

Thought analysis

Idea 1: First go through the binary tree, record the parent node of each node. And then, for the node p that they gave us, we keep looking for the upper nodes of P, all the way down to the root, and record the set of the upper nodes of P. Then, for the q node, keep looking for its upper node according to the record. In the process of searching, once the upper node is found to be included in the collection just now, it means that the latest common ancestor is found, and it directly returns.

Idea 2: If the current node is p or Q, return to that node. Otherwise, look for left and right children. If the left child does not contain P or Q, look for the right child, if the right child does not contain P or Q, look for the left child. The remaining case is that both the left and right children have a P or a Q, so we just return this node.

The ancestor node set is valid

/** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */
var lowestCommonAncestor = function(root, p, q) {
    if(root == null || root == p || root == q) return root;
    let set = new Set(a);let map = new WeakMap(a);let queue = [];
    queue.push(root);
    // Sequence traversal
    while(queue.length) {
        let size = queue.length;
        while(size --) {
            let front = queue.shift();
            if(front.left) {
                queue.push(front.left);
                // Record the parent node
                map.set(front.left, front);
            }
            if(front.right) {
                queue.push(front.right);
                // Record the parent nodemap.set(front.right, front); }}}// Construct the upper node set of P
    while(p) {
        set.add(p);
        p = map.get(p);
    }
    while(q) {
        // If the common nodes overlap, return directly
        if(set.has(q))returnq; q = map.get(q); }};Copy the code

So you can see that the entire binary tree has been traversed, and the time complexity is about order n, but the space complexity is high because of the hash table, so we’re going to use another way of traversing, which reduces the space cost a lot.

Depth first traversal

The code is very simple and beautiful, but it’s more important to understand the recursive invocation process, the code is executed from the top down, I recommend you to understand it from the bottom up, from the bottom left node, I believe you will understand the whole process.

var lowestCommonAncestor = function(root, p, q) {
    if (root == null || root == p || root == q) return root;
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    if(left == null) return right;
    else if(right == null) return left;
    return root;
};
Copy the code

The nearest common ancestor of a binary search tree

Given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 output: 6: node 2 and 8 of recent common ancestor is 6.Copy the code

Source: LeetCode problem 235

implementation

Binary search tree as a special binary tree, of course, can be used in the above two ways to achieve.

However, with the ordered nature of binary search trees, we can also write another version of deeply optimized traversal.

/** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */
var lowestCommonAncestor = function(root, p, q) {
    if(root == null || root == p || root == q) return root;
    // root. Val is bigger than p and q
    if(root.val > p.val && root.val > q.val) 
        return lowestCommonAncestor(root.left, p, q);
    // root. Val is smaller than p and q
    if(root.val < p.val && root.val < q.val) 
        return lowestCommonAncestor(root.right, p, q);
    else 
        return root;
};
Copy the code

We can also use a non-recursive approach:

var lowestCommonAncestor = function(root, p, q) {
    let node = root;
    while(node) {
        if(p.val > node.val && q.val > node.val)
            node = node.right;
        else if(p.val < node.val && q.val < node.val) 
            node = node.left;
        else returnnode; }};Copy the code

Are you impressed by the simplicity and elegance of binary trees? I hope you can enjoy the process of traversal, and then be sure to implement it yourself, to ensure that the data structure is familiar enough to enhance their own programming internal forces.

The path problem in binary trees

No.1 Diameter of a binary tree

Given a binary tree, you need to calculate its diameter. The diameter length of a binary tree is the maximum of the path length of any two nodes. This path might go through the root.

Example: Given a binary tree

          1
         / \
        2   3
       / \     
      4   5  
Copy the code

Return 3, whose length is either path [4,2,1,3] or [5,2,1,3].

Note: The length of the path between two nodes is expressed by the number of edges between them.

Source: LeetCode question 543

Train of thought

The diameter is essentially the maximum sum of the heights of the left and right subtrees of a node in a tree.

Notice that I’m talking about nodes in the tree, not the root node. Because here’s the thing:

1/2 / \ 4 5 / \ 8 6\7Copy the code

At this time, the path with the largest diameter is 8 -> 4 -> 2-> 5 -> 6 -> 7. The interface element is not the root node. This is where the problem needs special attention, otherwise there is no solution.

A preliminary solution

The goal has been determined, to find the maximum value of the height sum of the left and right subtrees of the node in the tree. Open dry!

/** * @param {TreeNode} root * @return {number} */
var diameterOfBinaryTree = function(root) {
    // Find the maximum depth
    let maxDepth = (node) = > {
      if(node == null) return 0;
      return Math.max(maxDepth(node.left) + 1, maxDepth(node.right) + 1);
    }
    let help = (node) = > {
        if(node == null) return 0;
        let rootSum = maxDepth(node.left) + maxDepth(node.right);
        let childSum = Math.max(help(node.left), help(node.right));
        return Math.max(rootSum, childSum);
    }
    if(root == null) return 0;
    return help(root);
};
Copy the code

Such a piece of code can be passed in LeetCode, but the time is not very satisfactory, why?

Because the repeated calls to maxDepth add a lot of unnecessary access to some of the nodes in the tree. Such as:

1/2 / \ 4 5 / \ 8 6\7Copy the code

Let’s see when node 8 is accessed, maxDepth(node 2) is accessed, and maxDepth(node 4) is accessed again. If the node is higher in the hierarchy, it will be accessed more frequently. The same is true for the remaining nodes 6 and 7. The number of visits per node is approximately O(logK)(if the current node is at layer K). So can we get this frequency down to order one?

And the answer is yes, so let’s optimize this algorithm.

Optimization method

var diameterOfBinaryTree = function(root) {
    let help = (node) = > {
        if(node == null) return 0;
        let left = node.left ? help(node.left) + 1: 0;
        let right = node.right ? help(node.right) + 1: 0;
        let cur = left + right;
        if(cur > max) max = cur; 
        // The return operation is critical
        return Math.max(left, right);
    }
    let max = 0;
    if(root == null) return 0;
    help(root);
    return max;
};
Copy the code

In this process, a global variable Max is set, and the tree is traversed with depth first. Every time a node is traversed, Max is updated, and the maximum height of the left and right subtrees of the current node is passed to the parent function from the bottom up by returning the value, so that each node can be accessed only once.

Now we submit our optimized code, and the time consumption is significantly reduced.

All paths of binary tree No.2

Given a binary tree, return all paths from the root node to the leaf node.

Note: A leaf node is a node with no child nodes.

Example:

Input: 1 / \ 2 3\5 Output: ["1 - > 2 - > 5"."1 - > 3"]
Copy the code

Explanation: The paths of all root nodes to leaf nodes are: 1->2->5, 1->3

Source: LeetCode question 257

The recursive method

Traversal is performed using DFS(depth-first traversal).

/** * @param {TreeNode} root * @return {string[]} */
var binaryTreePaths = function(root) {
    let path = [];
    let res = [];
    let dfs = (node) = > {
        if(node == null) return;
        path.push(node);
        dfs(node.left);
        dfs(node.right);
        if(! node.left && ! node.right) res.push(path.map(item= > item.val).join('- >'));
        // Delete a node from the path after it has been accessed
        path.pop();
    }
    dfs(root);
    return res;
};
Copy the code

Non-recursive solution

Let’s do it in a non-recursive way, just to review the implementation of a post-ordered traversal. Post-order traversal is also a concrete implementation of DFS. : : :

var binaryTreePaths = function(root) {
    if(root == null) return [];
    let stack = [];
    let p = root;
    let set = new Set(a); res = [];while(stack.length || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }
        let node = stack[stack.length - 1];
        // Leaf node
        if(! node.right && ! node.left) { res.push(stack.map(item= > item.val).join('- >'));
        }
        // The right child exists and the right child has not been accessed
        if(node.right && ! set.has(node.right)) { p = node.right; set.add(node.right); }else{ stack.pop(); }}return res;
};
Copy the code

No.3 Maximum path sum of a binary tree

Given a non-empty binary tree, return its maximum path sum.

In this case, a path is defined as a sequence from any node in the tree to any node. The path contains at least one node and does not necessarily pass through the root node.

Example:

Input: [-10,9,20, NULL, NULL,15,7] -10 / \ 9 20 / \ 15 7 Output: 42Copy the code

Question 124

Recursive solution

/** * @param {TreeNode} root * @return {number} */
var maxPathSum = function(root) {
    let help = (node) = > {
        if(node == null) return 0;
        let left = Math.max(help(node.left), 0);
        let right = Math.max(help(node.right), 0);
        let cur = left + node.val + right;
        // If the value of the path on a node is larger than Max, update Max
        if(cur > max) max = cur;
        // There is no turning point between right and left
        return Math.max(left, right) + node.val;
    }
    let max = Number.MIN_SAFE_INTEGER;
    help(root);
    return max;
};
Copy the code

Binary search tree

No.1 verify binary search trees

Given a binary tree, judge whether it is a valid binary search tree.

Suppose a binary search tree has the following characteristics:

The left subtree of a node contains only the number smaller than the current node. The right subtree of a node contains only the number greater than the current node. All left and right subtrees must themselves also be binary search trees.

Example 1:

Input: 2 / \ 1 3 Output:true
Copy the code

Question 98

Method 1: in order traversal

The value of the previous node is saved through the middle order traversal. When the current node is scanned, it is compared with the value of the previous node. If the value is greater than the previous node, the condition is met; otherwise, it is not a binary search tree.

/** * @param {TreeNode} root * @return {boolean} */
var isValidBST = function(root) {
    let prev = null;
    const help = (node) = > {
        if(node == null) return true;
        if(! help(node.left))return false;
        if(prev ! = =null && prev >= node.val) return false;
        // Save the current node in preparation for the next node traversal
        prev = node.val;
        return help(node.right);
    }
    return help(root);
};
Copy the code

Method two: DFS with upper and lower bounds

Binary search tree each node value, there is a upper and lower bounds, the process of depth-first traversal, if access to the left child, by the value of the current node to update the upper bound of the left child node, access to the right child at the same time, update the right child’s lower bound, as long as a node value of crossing the line, does not meet the conditions of the binary search tree.

  parent
  /    \
left   right
Copy the code

If this is part of a large binary tree (parent, left, and right are all actual nodes), then the order of all nodes must look like this:

. left, parent, right…

You can see that the strictest upper bound for the left child is this node, and the strictest lower bound for the right child is also this node. We update the upper and lower bounds according to this rule.

Recursive implementation:

var isValidBST = function(root) {
    const help = (node, max, min) = > {
        if(node == null) return true;
        if(node.val >= max || node.val <= min) return false;
        // The left child updates the upper bound, and the right child updates the lower bound
        return help(node.left, node.val, min)
                && help(node.right, max, node.val);
    }
    return help(root, Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER);
};
Copy the code

Non-recursive implementation:

var isValidBST = function(root) {
    if(root == null) return true;
    let stack = [root];
    let min = Number.MIN_SAFE_INTEGER;
    let max = Number.MAX_SAFE_INTEGER;
    root.max = max; root.min = min;
    while(stack.length) {
        let node = stack.pop();
        if(node.val <= node.min || node.val >= node.max)
            return false;
        if(node.left) {
            stack.push(node.left);
            // Update the upper and lower bounds
            node.left.max = node.val;
            node.left.min = node.min;
        }
        if(node.right) {
            stack.push(node.right);
            // Update the upper and lower boundsnode.right.max = node.max; node.right.min = node.val; }}return true;
};
Copy the code

No.2 converts an ordered array to a binary search tree

Convert an ordered array in ascending order to a highly balanced binary search tree.

In this case, a height-balanced binary tree is a binary tree where the absolute value of the height difference between the left and right subtrees of each node is less than 1.

Example:

Given an ordered array: [-10,-3,0,5,9], one possible answer is: [0,-3,9,-10, NULL,5], which can represent the following highly balanced binary search tree: 0 / \ -3 9 / / -10 5Copy the code

Source: LeetCode problem 108

The recursive implementation

/** * @param {number[]} nums * @return {TreeNode} */
var sortedArrayToBST = function(nums) {
    let help = (start, end) = > {
        if(start > end) return null;
        if(start === end) return new TreeNode(nums[start]);
        let mid = Math.floor((start + end) / 2);
        // Find the midpoint to create a node
        let node = new TreeNode(nums[mid]);
        node.left = help(start, mid - 1);
        node.right = help(mid + 1, end);
        return node;
    }
    return help(0, nums.length - 1);
};
Copy the code

Recursive programs are easy to understand, constantly calling help to complete the building of the whole tree. So how do we solve it with non-recursion? I think this is a question worth thinking about. I hope you can try it out, and if you really can’t think of it, you can refer to the non-recursive version I wrote below.

The idea is the same as the recursive version, but it is implemented using a stack to achieve the effect of DFS.

/** * @param {number[]} nums * @return {TreeNode} */
var sortedArrayToBST = function(nums) {
    if(nums.length === 0) return null;
    let mid = Math.floor(nums.length / 2);
    let root = new TreeNode(nums[mid]);
    // Note: 1. Index refers to the index of the current element in the array
    // 2. The value of each node is the midpoint of the interval, so the start attribute is the beginning of the interval, and the end attribute is the end
    root.index = mid; root.start = 0; root.end = nums.length - 1;
    let stack = [root];
    while(stack.length) {
        let node = stack.pop();
        // Node comes out, which itself contains a range, [start,... index,... end]
        [node.start, node.index-1]
        if(node.index - 1 >= node.start) {
            let leftMid = Math.floor((node.start + node.index)/2);
            let leftNode = new TreeNode(nums[leftMid]);
            node.left = leftNode;
            // Initialize the interval start, end, and index of the new node
            leftNode.start = node.start;
            leftNode.end = node.index - 1;
            leftNode.index = leftMid;
            stack.push(leftNode);
        }
        // The node. Index is in the middle of the node
        [node.index + 1, node.end
        if(node.end >= node.index + 1) {
            let rightMid = Math.floor((node.index + 1 + node.end)/2);
            let rightNode = new TreeNode(nums[rightMid]);
            node.right = rightNode;
            // Initialize the interval start, end, and index of the new node
            rightNode.start = node.index + 1; rightNode.end = node.end; rightNode.index = rightMid; stack.push(rightNode); }}return root;
};
Copy the code

The No.3 binary tree is expanded to a linked list

Given a binary (search) tree, expand it in place to a linked list.

For example, given a binary tree

1 / \ 2 5 / \ 3 4 6Copy the code

Expand it to:

1\2\3\4\5\6Copy the code

Source: LeetCode 114

recursively

Use the post-order traversal, traversal left and right children what do we do? Use the following image to illustrate (click to enlarge) :

/** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */
var flatten = function(root) {
    if(root == null) return;
    flatten(root.left);
    flatten(root.right);
    if(root.left) {
        let p = root.left;
        while(p.right) {
            p = p.right;
        }
        p.right = root.right;
        root.right = root.left;
        root.left = null; }};Copy the code

Non-recursive

Use a non-recursive sequential traversal, the same idea as before.

var flatten = function(root) {
    if(root == null) return;
    let stack = [];
    let visited = new Set(a);let p = root;
    // Start the sequential traversal
    while(stack.length || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }
        let node = stack[stack.length - 1];
        // If the right child exists and the right child has not been accessed
        if(node.right && ! visited.has(node.right)) { p = node.right; visited.add(node.right); }else {
            // The following is the key logic in the diagram
            if(node.left) {
                let p = node.left;
                while(p.right) {
                    p = p.right;
                }
                p.right = node.right;
                node.right = node.left;
                node.left = null; } stack.pop(); }}};Copy the code

No.4 Different binary search tree II

Given an integer n, generate all items made up of 1… N is a binary search tree composed of nodes.

Example:

Input: 3 output: [[1, null, 3, 2], [3, 2, null, 1], [3, 1, null, null, 2], [2,1,3], [1, null, 2, null, 3]] : The above output corresponds to the following five binary search trees of different structures: 1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3Copy the code

Problem 95

The recursive method

Create a subtree recursively

/** * @param {number} n * @return {TreeNode[]} */
var generateTrees = function(n) {
    let help = (start, end) = > {
        if(start > end) return [null];
        if(start === end) return [new TreeNode(start)];
        let res = [];
        for(let i = start; i <= end; i++) {
            // Left child set
            let leftNodes = help(start, i - 1);
            // Right child set
            let rightNodes = help(i + 1, end);
            for(let j = 0; j < leftNodes.length; j++) {
                for(let k = 0; k < rightNodes.length; k++) {
                    let root = newTreeNode(i); root.left = leftNodes[j]; root.right = rightNodes[k]; res.push(root); }}}return res;
    }
    if(n == 0) return [];
    return help(1, n);
};
Copy the code

Non-recursive solution

var generateTrees = function(n) {
    let clone = (node, offset) = > {
        if(node == null) return null;
        let newnode = new TreeNode(node.val + offset);
        newnode.left = clone(node.left, offset);
        newnode.right = clone(node.right, offset);
        return newnode;
    }
    if(n == 0) return [];
    let dp = [];
    dp[0] = [null];
    // I is the number of nodes in the subproblem: [1], [1,2], [1,2,3]... Increments until [1,2,3... n]
    for(let i = 1; i <= n; i++) {
        dp[i] = [];
        for(let j = 1; j <= i; j++) {
            // Left subtree set
            for(let leftNode of dp[j - 1]) {
                // Right subtree set
                for(let rightNode of dp[i - j]) {
                    let node = new TreeNode(j);
                    // The left subtree is shared
                    node.left = leftNode;
                    // The right subtree cannot be shared, but you can borrow a tree with the same number of nodes, adding an offset for each nodenode.right = clone(rightNode, j); dp[i].push(node); }}}}return dp[n];
};
Copy the code

So much for sharing this time. You can see how much knowledge there is about data structures and algorithms, but with the help of this series, I’m sure you’ll be able to get your hands on data structures and algorithms. Here’s the Github repository for this series.

Making the warehouse

Online reading address for this series

In addition, my blog has been sorted out now, the address is here, click open.