To the chase

105. Construct a binary tree by traversing pre-order and middle-order sequences

Preorder and inorder of a tree are given. Construct a binary tree and return its root node.

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

Resolution:

First of all, let’s understand the order of binary tree foreorder and middle order traversal:

Front order: root -> left -> right

Middle order: left -> root -> right

Looking for an entry point

To implement a binary tree, the first step is to find the root node, and then recurse to the left and right nodes. According to the traversal order of the pre-traversal, we can know that the first node of the pre-traversal is the root node, so we can think that in the process of constructing a binary tree, we can take the first node of the pre-traversal as the root node of the recurrence.

Therefore, the underlying logic to solve this problem is to find out: to find out the sequential traversal number group of left and right nodes respectively for recursion.

Find a regular

Taking example 1 as a reference, if the first digit of the current sequential traversal is 3, the first node of the tree node must be 3, which is the characteristic of the sequential traversal. So what is his left root node? The second is 9, and the left tree could theoretically be 9 based on the rule of prior traversal, but if there is no root on the left, then this 9 could be the root of the right tree. So we’re going to extract information from the order traversal to determine whether the second 9 is left or right.

Highlight: According to the principle of middle-order traversal, the first 3 in the pre-order traversal ranks the second in the middle-order traversal, so it indicates that the second place in the middle-order traversal is under the left tree of the root node 3

So we can extract 3 as the root in the middle order traversal, all the nodes on the left side of the tree, and all the nodes on the right side of the tree.

Extract the left and right nodes again as the root node recursion

First we find the position of the root node in the right tree of the preceding traversal (used to extract all left and right nodes).

const rootIndex = inorder.indexOf(preorder[0])
Copy the code

The first node of the left tree must be the root, rootIndex is the position of the root node in the middle-order traversal, so in the middle-order traversal, the subscript less than rootIndex is the left tree, equal to rootIndex is the root, and the subscript greater than rootIndex is the right tree. So we can iterate left and right again, recursively.

The left tree

We can recursively construct a binary tree again with the left node as the root node:

res.left = buildTree(preorder.slice(1,rootIndex + 1), inorder.slice(0, rootIndex))
Copy the code

Preorder. slice(1,rootIndex + 1: remove the elements already used as the root node, and take the left side of rootIndex as the root node for recursion

Inorder. slice(0, rootIndex): Extract all the left side of rootIndex as all elements of the right node for recursion.

The right tree

Construct right node binary tree:

    res.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1))

Copy the code

Preorder. slice(rootIndex + 1: after removing the root node, the left node is left with the right node.

Inorder. slice(rootIndex + 1): All right nodes to the right of rootIndex

Complete code:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
  if (inorder.length === 0) return null
    const res = new TreeNode(preorder[0])
    const rootIndex = inorder.indexOf(preorder[0])
    res.left = buildTree(preorder.slice(1,rootIndex + 1), inorder.slice(0, rootIndex))
    res.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1))
    return res
};
Copy the code

The thesis process is abstract and not easy to be represented by animation. It is easier to understand only when it is sensitive to the preorder and middle order traversal of binary tree.