This is the 17th day of my participation in the August Challenge

Rebuild the binary tree

Offer 07. Rebuild binary tree

Enter the results of preorder and middle order traversal of a binary tree, please rebuild the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers.

For example, given

Preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Copy the code

Return the following binary tree:

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

Limit: 0 <= Number of nodes <= 5000

Answer key

First of all, we need to understand the node traversal order of pre-order traversal and middle-order traversal.

Foreorder traversal: root -> left -> right

Middle order traversal: left -> root -> right

According to the title, we can get:

The root node of the preceding traversal, and its position in the middle traversal is left subtree and right subtree. The index obtained by middle order traversal can help us divide the pre-ordinal groups, so we can get the leaf nodes recursively through the obtained array, and finally assemble a complete tree by backtracking.

 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
 / * * *@param {number[]} preorder
  * @param {number[]} inorder
  * @return {TreeNode}* /
 var buildTree = function(preorder, inorder){
   if(preorder.length === 0) return null
   const cur = new TreeNode(preorder[0]) // Get the root node
   const index = inorder.indexOf(preorder[0]) // Get the position of the root node in the ordinal group
   cur.left = buildTree(preorder.slice(1,index+1),inorder.slice(0,index))
   cur.right = buildTree(preorder.slice(index+1),inorder.slice(index+1))
   return cur
 }
Copy the code

Implement queues with two stacks

Offer 09. Implement queues with two stacks

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

Tip:

  • 1 <= values <= 10000
  • At most 10000 calls are made to appendTail and deleteHead

Answer key

Queue: first in first out Stack: last in first out

The division of labor of the two stacks is different, one is the joining stack, the other is the leaving stack, and each is responsible for joining and leaving the team.

In the queue operation, you can directly press into the queue stack. In the queue operation, you need to check whether there is data in the queue stack first. If there is no data, you need to import from the queue stack to the queue stack and then out of the stack.

 var CQueue = function(){
   this.stack1 = [] / / team stack
   this.stack2 = [] / / out of the stack
 };
 / * * *@param {number} value
  * @return {void}* /
 CQueue.prototype.appendTail = function(value){
   this.stack1.push(value)
 };
 ​
 / * * *@return {number}* /
 CQueue.prototype.deleteHead = function(){
   if(this.stack2.length){
     return this.stack2.pop()
   }else{
     while(this.stack1.length){
       this.stack2.push(this.stack1.pop())
     } 
     if(!this.stack2.length){
       return -1;
     }else{
       return this.stack2.pop()
     }
   }
 };
 ​
 /** * Your CQueue object will be instantiated and called as such: * var obj = new CQueue() * obj.appendTail(value) * var param_2 = obj.deleteHead() */
Copy the code

Practice every day! The front end is a new one. I hope I can get a thumbs up