Hello everyone, I am quick-frozen fish 🐟, a river front 💦, like the garish 💐, continuous sand sculpture 🌲 Welcome friends to add my wechat: Sudongyuer pull you into the group, discuss together, looking forward to growing together with everyone

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

Of course, learning is also focused, as the front end we do not need to fully grasp the algorithm like back-end development, some of the more partial, not practical type and solution method, as long as a little understanding.

The title 🦀

Offer 07. Rebuild binary tree

The difficulty of medium

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

🌵

  • Adopt the idea of divide and rule
  • The root node is determined according to the first node in the preceding order traversal, and the number of left and right subtrees is determined according to the position of the root node in the middle order traversal, and then the left and right subtrees in the middle order traversal and the preceding order traversal respectively.
  • Then do the same for the left and right subtrees

Experience ❤️

  • Be sure to draw more
  • Be sure to draw more
  • Be sure to draw more

Source 🔥

/** * 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 index of the root node in the preceding traversal
     const index=inorder.indexOf(cur.val)

     // Split left and right subtrees in middle order traversal based on index
     const preorderLeft=preorder.slice(1,index+1)


    // Split left and right subtrees in middle order traversal based on index
     const preorderRight=preorder.slice(index+1)    


    // Split left and right subtrees in middle order traversal based on index
     const inorderLeft=inorder.slice(0,index)
    // Split left and right subtrees in middle order traversal based on index
     const inorderRight=inorder.slice(index+1)  

     // Build the left subtree
     cur.left=buildTree(preorderLeft,inorderLeft)
     // Build the right subtree
     cur.right=buildTree(preorderRight,inorderRight)
     return cur
};
Copy the code

Time complexity :O(n)

Space complexity :O(n)

Conclusion 🌞

So the “LeetCode” of The LeetCode of the algorithm chapter refers to the offshor-07 reconstruction of binary tree ⚡️. There is no shortcut to the algorithm, so we can only write and practice more and summarize more. The purpose of the article is actually very simple, which is to urge myself to complete the algorithm practice and summarize and output. I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.

Add me on wechat: Sudongyuer, invite you to join the group, learn front end together, become a better engineer ~ (group QR code here -> front end to go to bed early, qr code expired to see the link in the boiling point of the comments, I will put the latest QR code in the comment section, of course, you can also add my wechat I pull you into the group, after all, I am also interesting front end, It’s not bad to know me 🌟 ~ PS: the company is in the front of recruitment recently, welcome friends to consult, coordinates chengdu, my VX: Sudongyuer, or direct delivery mailbox [[email protected]]