Topic describes

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] returns the following binary tree:

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

Limitations:

0 <= Number of nodes <= 5000

Their thinking

For a binary tree, the first element of the pre-order traversal is the parent node of the binary tree. According to the parent node, we can find the position index of the parent node in the middle order traversal. According to the index, we can divide the middle order traversal into left and right sub-trees, which are also middle order traversal. We can also find pre-traversal of left and right subtrees according to index. So we can recursively call the function to find the parent nodes of the left and right subtrees, and assign them to Node. left and Node. right. The condition to end the recursion is that there is only one element in the preceding array, which means that there is only the root element, the left and right subtrees are empty, and this node is returned.

AC code

/* Order traversal: left subtree traversal + right subtree traversal + right subtree traversal: left subtree traversal + right subtree traversal + right subtree traversal + node traversal: left subtree traversal + right subtree traversal + node traversal: left subtree traversal + right subtree traversal + node traversal -> The length of the left subtree and the length of the right subtree intercept the middle traversal of the left subtree, the middle traversal of the right subtree intercept the front traversal of the left subtree, the front traversal of the right subtree recursively rebuild the binary tree */
class Node {
    constructor(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right
    }
    show() {
        console.log(this.data); }};function rebuildTree(pre,mid) {
    if (pre.length === 0) {
        return null;
    }
    if (pre.length === 1) {
        return new Node(pre[0])}const data = pre[0];
    const index = mid.indexOf(data);
    const midLeft = mid.slice(0,index);
    const midRight = mid.slice(index+1);
    const preLeft = pre.slice(1,index+1);
    const preRight = pre.slice(index+1);
    const node = new Node(data);
    node.left = rebuildTree(preLeft,midLeft);
    node.right = rebuildTree(preRight,midRight);
    return node;
 }
 let preorder = [3.9.20.15.7];
 let inorder = [9.3.15.20.7];
console.log( rebuildTree(preorder,inorder));
Copy the code

conclusion

For any tree, the form of the preceding traversal is always

[root node, [pre-traversal result of left subtree], [pre-traversal result of right subtree]]Copy the code

That is, the root node is always the first node in the preceding traversal. And the middle order traversal is always

[[middle-order traversal result of left subtree], root node, [middle-order traversal result of right subtree]]Copy the code

As long as we locate the root node in the middle traversal, we can know the number of nodes in the left and right subtrees respectively. Since the length of pre-order traversal and middle-order traversal of the same subtree is obviously the same, we can locate all the left and right parentheses in the above form in the result of pre-order traversal.

In this way, we know the results of pre-order traversal and middle-order traversal of the left subtree, as well as the results of pre-order traversal and middle-order traversal of the right subtree. We can construct the left and right subtrees recursively, and then connect the two subtrees to the left and right positions of the root node.

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