Clock in the next day, chose my brush list haven’t done the topic, the first medium difficulty is a binary tree algorithm, the data structure of binary tree as a basic, are very common in the study and work, it is worth a brush, today the problem is a according to the order and the order before the array for tree traversal algorithm, please see:

First, look at the problem

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]

Return the following binary tree:

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

Limitations:

  • 0 <= Number of nodes <= 5000

Second, organize your thoughts

Tree front, middle and back order traversal all belong to the algorithm foundation, do not understand please reflect on their own. First of all, by analyzing the topic, it can be concluded that:

  1. If you already have an array traversed in advance, it’s easier and easier to build a tree manually from the root node
  2. The process of building a subtree of a binary tree uses the same logic as your parents, so it’s easy to think of recursion
  3. Since there are no duplicate numbers in any of the results, you don’t have to worry about more than one case in the same order
  4. Consider the boundary case where the node is zero

Based on the above analysis, I wrote the following code

/** * 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 ! == inorder.length || preorder.length ==0 || inorder.length == 0) {
        return null
    }
    let tree = new TreeNode(preorder[0])
    let idx = inorder.indexOf(preorder[0])
    tree.left = buildTree(preorder.slice(1, idx + 1), inorder.slice(0, idx))
    tree.right = buildTree(preorder.slice(idx + 1), inorder.slice(idx + 1))
    return tree
};
Copy the code

This solution, which is the most common, is bad because it uses slice() multiple times, creating multiple arrays.

If we can get the loss of other smaller way subtree and sequence traversal in the preamble of the results, it can improve the performance of the algorithm, and the subsequent reference other people’s code is optimized, the way to the child first and at the end of the index tree traversal results through the participation in the form of recorded, dispense with the need that generates a new array, a substantial increase in performance:

/ * * *@param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}* Algorithm variables have been renamed for readability *@rootIdx Index * of the current node in preorder@srtIdx The current tree traversal starts at the index * in inorder@endIdx The end index of the current tree traversal in inorder */
var buildTree = function (preorder, inorder, rootIdx,srtIdx,endIdx) {
    if(rootIdx==undefined){
        rootIdx=srtIdx=0
        endIdx=inorder.length-1
    }
    if (srtIdx>endIdx) return null
    let tree = new TreeNode(preorder[rootIdx])
    // Since all nodes have different values, we can use indexOf to get the index
    let inRtIdx = inorder.indexOf(preorder[rootIdx])
    tree.left = buildTree(preorder, inorder, rootIdx + 1,srtIdx,inRtIdx-1)
    tree.right = buildTree(preorder, inorder, rootIdx + (inRtIdx-srtIdx)+1,inRtIdx+1,endIdx)
    return tree
};
Copy the code

In this algorithm, the range of the current tree in the Inorder array is recorded. For the current tree, the root node index (leftIdx) of the left subtree is the current root node index +1 (rootIdx+1) in the preceding traversal, and the root node index (rightIdx) of the right subtree is rightIdx. That is, the index of the current root node + the length of the left subtree +1. Therefore, the index range of the tree is needed to assist the calculation of the length of the left subtree, thus avoiding the performance loss caused by using slice.

Third, summary

When I first got the topic, I had no clue at all. I could only think of starting from the root node, and even failed to figure out the recursion method. I realized that my foundation was weak.

Later, after reference, the for loop used in the first writing was tedious and unattractive, and then I realized that indexOf could solve the problem by referring to other people’s writing methods, which was another lack of understanding of THE commonly used API in JS.

Although the method of optimization thought for a long time or did not think how to do, is suddenly enlightened after learning. (meaning it took two hours to figure out the logic)

Although it is only a common medium difficulty binary tree problem, it is to make myself aware of a lot of deficiencies and weaknesses, continue to make efforts.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign