## Front and middle order traversal sequence construction binary tree, recursion + hash table, JavaScript, detailed comments

LeeChen 2021-01-21 04:51:48
middle order traversal sequence construction

Their thinking ：

1. Refer to the Many solutions , Gradually optimize （ Supplement the solution of foreign tycoons ） and The demo 105. Construction of binary trees from traversal sequences of preorder and middle order .
2. Suppose there is a binary tree as follows ：
`````` 1
/ \
2 3
/ \ / \
4 5 6 7
Copy code ``````

The result of preorder traversal is : `[1,2,4,5,3,6,7]` The result of middle order traversal is : `[4,2,5,1,6,3,7]`

1. You can take it from the root node 1, Split into two subtrees , as follows ：

The left subtree ：

`````` 2
/ \
4 5
Copy code ``````

The result of preorder traversal is : `[2,4,5]` The result of middle order traversal is : `[4,2,5]`

Right subtree ：

`````` 3
/ \
6 7
Copy code ``````

The result of preorder traversal is : `[3,6,7]` The result of middle order traversal is : `[6,3,7]`

1. We can follow the steps 3 Laws , Calculate the index in the original array corresponding to the front middle order traversal of the left and right subtrees , You can know their corresponding values ：

• The preorder traversal index of the left subtree ：
``````preLeft = preLeft + 1, // The preorder of the left subtree traverses the left boundary
preRight = preLeft + nodeCount, // The current left border plus the number of subtree nodes , That is, the preorder of the left subtree traverses the right boundary
Copy code ``````
• Middle order traversal index of left subtree ：
``````inLeft = inLeft, // The middle order of the left subtree traverses the left boundary
inRight = rootIndex - 1, // The middle order of the left subtree traverses the right boundary
Copy code ``````
• The preorder traversal index of the right subtree ：
``````preLeft = preLeft + nodeCount + 1, // The current left boundary plus the number of subtree nodes plus 1, That is, the preorder of the right subtree traverses the left boundary
preRight = preRight, // The preorder of the right subtree traverses the right boundary
Copy code ``````
• The middle order traversal index of the right subtree ：
``````inLeft = rootIndex + 1, // The middle order of the right subtree traverses the left boundary
inRight = inRight, // The middle order of the right subtree traverses the right boundary
Copy code ``````
2. Through the steps 4 Analysis of , We can recurse according to the following logic ：

• For each recursion `preorder[preLeft]` The value of generates a root node .
• Through `preorder[preLeft]` Find it in `inorder` Position in `rootIndex`, Calculate the index of the front middle order traversal of the subtree in the original array , Recursion of the next layer is carried out respectively .
• Every time I recurs ,`inorder` The position of each value in is fixed , So just use... Before recursion Map Cache the relationship between all values and indexes , After use `O(1)` The query can be completed with the time complexity of .
• The left and right subtrees generated by the lower layer recursion , Connect to the current root node .
• When the recursion completes, the current root node is returned , Recursive connection for the next layer .
• `preorder` and `inorder` After all the values in are generated by nodes , That is to say, the generation of the whole binary tree is completed .
``````/**
* 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) {
/**
* @description  Use the pre middle order to traverse the fragment of the result , Recursively generate a binary tree
* @param {number} preLeft // The left boundary of each subtree in the preorder traversal
* @param {number} preRight // The right boundary of each subtree in the preorder traversal
* @param {number} inLeft // The left boundary of each subtree in the middle order traversal
* @param {number} inRight // The right boundary of each subtree in the middle order traversal
* @return {TreeNode}
*/
function buildBinaryTree(preLeft, preRight, inLeft, inRight) {
// When the left bound of the truncated array fragment is larger than the right bound , Indicates that the current array used to construct the subtree is empty , Exit loop
if (preLeft > preRight) {
// When the array is empty , It means that there is no node to generate at present , return null
// Let the node of the upper layer left and right Pointer to null
return null;
}
// Cache the value of the root node
const rootVal = preorder[preLeft];
// Create a node with the current value , It is the root node of a tree
const root = new TreeNode(rootVal);
// Find the position of the current root node in the array
const rootIndex = inorder.indexOf(rootVal);
// The difference between the left bound of the middle order traversal and the root node is the number of nodes in the subtree
// Because the left boundary will always exist , So counting to the left always gets the number of nodes in the subtree
const nodeCount = rootIndex - inLeft;
// Calculate the index of the left subtree of the array , Down the recursive
// Connect the current root node with the generated left subtree
root.left = buildBinaryTree(
preLeft + 1, // The preorder of the left subtree traverses the left boundary
preLeft + nodeCount, // The current left border plus the number of subtree nodes , That is, the preorder of the left subtree traverses the right boundary
inLeft, // The middle order of the left subtree traverses the left boundary
rootIndex - 1, // The middle order of the left subtree traverses the right boundary
);
// Calculate the index of the right subtree of the array , Down the recursive
// Connect the current root node with the generated right subtree
root.right = buildBinaryTree(
preLeft + nodeCount + 1, // The current left boundary plus the number of subtree nodes plus 1, That is, the preorder of the right subtree traverses the left boundary
preRight, // The preorder of the right subtree traverses the right boundary
rootIndex + 1, // The middle order of the right subtree traverses the left boundary
inRight, // The middle order of the right subtree traverses the right boundary
);
// Return the root node for the upper node to connect
return root;
}
// Generate a binary tree and return
return buildBinaryTree(0, preorder.length - 1, 0, preorder.length - 1);
};
Copy code ``````

https://javamana.com/2021/01/20210121044620188y.html