This is the 18th day of my participation in the August Genwen Challenge.More challenges in August

Brush questions, please go to LeetCode to brush questions together when you have time. By brushing questions, you can consolidate the data structure and algorithm foundation. The accumulated improvement is really great, especially now all the better factories will test the algorithm

If you also want to brush the algorithm of the plan, can encourage each other to exchange learning

Today’s content refers to questions 7 and 9 in offer(version 2) in leetCode

Let’s get started

Rebuild the binary tree

The title goes like this:

Enter the results of pre-order traversal and middle-order traversal of a binary tree, build the binary tree and return its root node.

It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null, 15,7]Copy the code

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Copy the code

Limitations:

0 <= Number of nodes <= 5000Copy the code

knowledge

  • The first element in a pre-traversal list is always the root node, which in this case is 3
  • Then find the root node in the middle-order traversal list and divide the middle-order traversal list into
    • In this case it is[left subtree (9), root (3), right subtree (15,20,7)]
  • Since the length of the pre-order traversal list and the middle-order traversal list in the same subtree is the same, the division in the pre-sequence list can be obtained
    • Root (3), left subtree (9), right subtree (20,15,7)

Such as

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

In this binary tree, the pre-order traversal is [1, 2, 4, 5, 3] and the middle-order traversal is [4, 2, 5, 1, 3].

First find the position of root element 1 in the middle-order traversal list, and get

  • The left subtree in the preceding traversal list isTwo, four, five, the right subtree is3
  • The left subtree in the middle order traversal list is4, 2, 5, the right subtree is3

So once you have that sorted out, then you can start to sort out your thoughts. How do you do that

// This is a function that defines a binary tree node
function TreeNode(val){
    this.val = val
    this.left = this.right = null
}
Copy the code

Idea 1: Recursion

Find the root first

Then, according to the root, the middle order traversal list is divided into left branches and right to go

And then we recurse on the left and right branches, find the roots, cut them out, recurse again

Slice (start,end) returns an array from a specified range. Start subscript (including start), truncated to end end. Not passing the end is to the end

/ / Input: preorder =,9,20,15,7 [3], inorder =,3,15,20,7 [9]
function buildTree(preorder, inorder){
    if(! preorder.length || ! inorder.length)return null
    const root = preorder[0] / / the root node
    const node = new TreeNode(root) // Create a binary tree instance
    const index = inorder.indexOf(root) // The subscript of the root node in the middle traversal list is 1
    
    // The first sequence table [9] is the left subtree
    node.left = buildTree( preorder.slice(1, index+1), inorder.slice(0, index) )
    // right subtrees recursively spread over new preorders [20,15,7] and middle orders [15,20,7]
    // 20 becomes the new root, 15 is the left subtree, and 7 is the right subtree
    node.right = buildTree( preorder.slice(index+1), inorder.slice(index+1))return node
}
Copy the code

Root 3 is found for the first time, left is foreorder [9] and middle order [9], right is foreorder [20,15,7] and middle order [15,20,7].

Then recursively find the new roots as 9 and 20, left as anteorder [] and middle order [], right as anteorder [15], and middle order [7].

The recursion then returns two NULls, the new roots 15 and 7

If [15] and [7] do not have the same root, there will be no branch

Implement queues with two stacks

The title goes like this:

Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)

Example 1

Input: [" CQueue appendTail ", ""," deleteHead ", "deleteHead"] [[], [3], [], []] output: [3, null, null, 1]Copy the code

Example 2

Input: [" CQueue deleteHead ", ""," appendTail ", "appendTail", "deleteHead", "deleteHead"] [[], [], [5], [2], [], []] output: [null, 1, null, null, 5, 2]Copy the code

limit

1 <= values <= 10000 Calls to appendTail and deleteHead are performed at most 10000 timesCopy the code

instructions

["CQueue","appendTail","deleteHead","deleteHead"] This represents the operation on each line of code [[],[3],[],[]] This represents the parameters required for each line of code. Examples: CQueue: creates a new CQueue object with []. This operation does not require the appendTail appendTail() operation. The corresponding element to be operated on is 3 deleteHead, which means that a deleteHead operation is performed. The corresponding parameter is [], which means that the operation does not need parametersCopy the code

Using stack to realize queue, first of all, we must know the execution rules of stack and queue

  • The stack is first in, then out
  • Queues are first in, first out

So the general idea is to create two stacks. When append is added to stack 1, delete is added to stack 2 from back to front. This is equivalent to flipping the task list of stack 1, and then removing it from stack 2 in order to achieve the effect of first-in, first-out

Idea 1

// Create a constructor that defines two stacks
let CQueue = function() {
    this.stack1 = []
    this.stack2 = []
}
// Add two methods for the constructor to push and push
CQueue.prototype.appendTail = function(value) {
    // Stack 1 is added as it is pushed
    this.stack1.push(value)
}

CQueue.prototype.deleteHead = function() {
    if(this.stack2.length){
        // If there is a task on stack 2, it will be removed directly from the stack
        return this.stack2.pop()
    }else{
        // If not, add tasks from stack 1 back to stack 2
        while(this.stack1.length){
            this.stack2.push(this.stack1.pop())
        }
        // Then execute the task on stack 2
        // If there are no more tasks on stack 2, return -1
        if(!this.stack2.length){
            return -1
        }else{
            return this.stack2.pop()
        }
    }
}
Copy the code

Today’s brush questions here, if you also want to brush questions, you can encourage each other to exchange

conclusion

Praise and support, hand left lingering fragrance, and have honor yan

Thank you for being here!