Make writing a habit together! This is the 9th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Hi, I’m the watermelon guy. Today we are going to talk about a somewhat difficult binary tree algorithm problem: preorder and middle order traversal sequence to construct a binary tree.

Given two integer arrays preorder and inorder, where preorder is a preorder traversal of a binary tree and inorder is a middle-order traversal of the same tree, construct a binary tree and return its root node.

Example 1:

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

Example 2:

Input: preOrder = [-1], inorder = [-1] output: [-1]Copy the code

LeetCode

Leetcode-cn.com/problems/co…

Train of thought

The core of this problem is to make good use of the pre-order traversal and middle-order traversal properties of binary trees.

Let’s look at this binary tree in the example.

Its preceding traversal is: [3,9,20,15,7]

The middle-order traversal is: [9,3,15,20,7]

A pre-order traversal is characterized by visiting the root node first, then the left and right nodes. So the first element in the sequence is the root of the whole tree.

By traversing the remaining nodes after removing the first element, we can actually find a certain index position and divide these nodes. After segmentation, the left side is the set of left nodes and the right side is the set of right nodes.

Take a fancy to order traversal again, in order traversal what characteristics. Middle order traversal Traversal first visits the left node, then the root node, and finally the right node.

We know what the root node is by pre-order traversal, and then we find the root node in mid-order traversal.

At this point, the left of the root node position is all the nodes of the left subtree of the root node (because the middle order traverses left -> root -> right). At this point, we can also calculate the number of left subtrees.

We get the number of left subtrees, and then we go back to the preceding traversal, and we figure out the array of left subtrees.

Here we get the pre-order traversal group and the mid-order traversal group of the left subtree.

We pass these two arrays to the recursive function, and the recursion is formed.

The same thing with the right subtree, I won’t go into it here.

Code implementation

Let me show you my code implementation.

function buildTree(preorder, inorder) {
  if (preorder.length === 0) return null;
  const first = preorder[0];
  const root = new TreeNode(first);
  // The position of the root node in the middle-order traversal
  const idx = inorder.indexOf(first);

  root.left = buildTree(
    preorder.slice(1, idx + 1),
    inorder.slice(0, idx)
  );
  root.right = buildTree(
    preorder.slice(idx + 1),
    inorder.slice(idx + 1));return root;
};

Copy the code

Every time we find the position of the root node in the middle order traversal, idx, we find the cut position of the array. Cut preorder and Inorder respectively, find the left and right subtrees’ respective pre-order traversal and middle-order traversal number groups, and then recurse. The recursive end condition is that the array is empty.

This implementation has the advantage of being readable and less prone to writing errors.

But in terms of efficiency, it could be better, and there are two things that could be improved:

  • Each time we copy the old array to create a new one, we can avoid copying by maintaining two pairs of array beginning and end indexes

  • It is inefficient to traverse the Inorder array each time to find the root node. You can use hash tables to cache the mapping of values to indexes at this point.

I don’t like the loss of readability caused by this extreme optimization. But I have to talk to you about optimizing your thinking.

After using these two schemes, I have to use a new recursive function, because the parameters have changed. In this case, you can give the recursive functions _buildTree or MyBuildTree or f (function), r (recursion).

I’m not happy with any of the names here, but I want to use buildTree. If only JavaScript supported true polymorphic writing like Java. Java Script you fake Java.

function buildTree(preorder, inorder) {
  const map = {};
  for (let i = 0; i < inorder.length; i++) {
    map[inorder[i]] = i;
  }
  return _buildTree(
      preorder, inorder, map,
      0, preorder.length,
      0, inorder.length
  );
};

function _buildTree(preorder, inorder, map, pL, pR, iL, iR) {
  if (pL >= pR) return null;
  const first = preorder[pL];
  const root = new TreeNode(first);
  const idx = map[first];
  const leftSize = idx - iL;

  root.left = _buildTree(
    preorder, inorder, map,
    pL + 1, pL + 1 + leftSize,
    iL, iL + leftSize
  );
  root.right = _buildTree(
    preorder, inorder, map,
    pL + leftSize + 1, pR,
    idx + 1, iR
  );
  return root;
};

Copy the code

This implementation has a dizzying number of recursive function parameters and is very prone to write errors when calculating the index, but it does run more efficiently than the first implementation.

At the end

Code is written for people, not machines, but by the way computers can execute it.

There is a tradeoff between readability and performance depending on the scenario.

If it is business logic code with no extreme performance requirements, please write human-readable code with priority.

If it’s low-level non-business code that focuses on performance, such as the STL library in C++, write code with extreme performance, and readability can be compromised. But this requires you to spend more time writing code, and you need to have enough test cases to get it right.

If you go to an interview to do an algorithm, don’t try to write a perfect best implementation all at once. After you write the first version, refine it a little bit. The interviewer wants to test your code optimization skills and thinking.

I am front-end watermelon brother, welcome to pay attention to me.

This article was first published on my public account: front-end watermelon brother