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

Tip:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • Preorder and inorder have no repeating elements
  • Inorder both appear in preorder
  • Preorder is guaranteed to be a pre-traversal sequence of a binary tree
  • Inorder is guaranteed to be a middle-order traversal sequence of a binary tree

The recursive traversal

Train of thought

In this problem, we are going to restore a tree according to the preceding and middle order traversal of the tree

So we can do it recursively

Condition 1: First of all, we can find the value of root node of the tree through the sequential traversal

Condition 2: We can find the location information of root node rootIndex in the subsequent traversal

Condition 3: The number of left subtrees must be the same regardless of whether they are traversed pre-order or middle-order

From the above two conditions, we can get one message:

Former sequence traversal [root, leftChildPre, rightChildPre]

  • LeftChildPre: Pre-traversal of the left subtree
  • RightChildPre: Pre-traversal of the right subtree

In sequence traversal [leftChildOrder, root, rightChildOrder]

  • LeftChildOrder: Middle-order traversal of the left subtree
  • RightChildOrder: Middle-order traversal of the right subtree

Then we can deal with it like this:

  • LeftChildPre and leftChildOrder are traversed through the left subtree to generate the left subtree
  • The right subtree is generated by traversing rightChildPre and rightChildOrder with the preceding and middle order of the right subtree
  • Then splice the left and right subtrees to the root node

At this point, the train of thought is over

See code comments for concrete implementation

var buildTree = function (preorder, inorder) {
    // Get the root node by traversing the first node
    var rootNode = preorder[0]
    // findIndex is used to obtain the location of the rootNode in the sequential traversal
    var rootIndex = inorder.findIndex(item= > item === rootNode)
    // Get the result of the left subtree traversal according to rootIndex
    var leftChildPre = preorder.slice(1.1 + rootIndex)
    // Get the result of the right subtree
    var rightChildPre = preorder.slice(1 + rootIndex)
    // Obtain the middle-order traversal result of the left subtree according to rootIndex
    var leftChildOrder = inorder.slice(0, rootIndex)
    // Get the middle-order traversal result of the right subtree
    var rightChildOrder = inorder.slice(1 + rootIndex)
    // Finally declare two variables to hold the restore results of the left and right subtrees
    var leftChildRoot, rightChildRoot
    // Focus, recursive exit
    // If the number of nodes in the left subtree is less than or equal to 1, there is only one node or null
    if(leftChildPre.length <= 1) {// Generate a single-node tree if the left subtree has nodes, otherwise null
        leftChildRoot = leftChildPre.length > 0 ? new TreeNode(leftChildPre[0) :null
    }else{
        // If the number of nodes is greater than 1, continue the recursive processing
        leftChildRoot = buildTree(leftChildPre, leftChildOrder)
    }
    / / same as above
    if(rightChildPre.length <= 1){
        rightChildRoot = rightChildPre.length > 0 ? new TreeNode(rightChildPre[0) :null
    }else{
        rightChildRoot = buildTree(rightChildPre, rightChildOrder)
    }
    // Connect the left and right subtrees under the root node
    var root = new TreeNode(rootNode, leftChildRoot, rightChildRoot)
    
    return root
};
Copy the code