[B] [C] [D]

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 和 inorderThere are no repeating elements
  • inorderAll appear inpreorder
  • preorderIs guaranteed to be a binary tree traversal sequence
  • inorderIs guaranteed to be a middle-order traversal sequence of a binary tree

The answer to this question is as follows:

  1. The order of foreorder traversal is left to root, and the order of middle order traversal is left to root right, sopreorder[0]Is the value of the current child root node
  2. Find the value ininorder, the left side is the sequence in the left subtree, and the right side is the sequence in the right subtree
  3. After obtaining the order traversal in the left and right subtrees, the result of the order traversal in the preceding and middle subtrees is only different in order, but the sequence length is the same, so the sequence length of the order traversal in the left subtree can be usedpreorderObtain the left subtree traversal sequence, and the rest is the right subtree traversal sequence
  4. The root node can then be created from the value of the root node, and the left and right subtrees can be created recursively based on the sequence of preceding and middle traversal of the left and right subtrees
  5. Return the root node of the binary tree

The animation is shown below:

The first version of the code is as follows:

Var buildTree = function(preorder, inorder) {// If (preorder. Length === 0) return null; Const root = new TreeNode(preorder.shift()), ind = inorder.indexof (root.val); Root.left = buildTree(preorder.splice(0,ind),inorder.splice(0,ind)); root.left = buildTree(preorder.splice(0,ind)); Root. right = buildTree(preOrder,inorder.splice(1)); root.right = buildTree(preOrder,inorder.splice(1)); // Return root; };Copy the code

After this version of the code is submitted, it only beats about 50% of the users, because it needs to intercept the pre-order and middle-order traversal sequence of the left and right subtrees in the recursive process, which increases the execution time and space complexity.

Here, we can maintain the start and end subscripts of the preorder traversal sequence of the current subtree, and the start and end subscripts of the middle order traversal sequence instead of intercepting the preorder and middle order traversal sequence, so as to achieve the purpose of building the left and right subtrees recursively.

The optimized code is as follows:

Var buildTree = function(preorder, inorder) {var buildTree = function(preorder, inorder) { Function build(preStart,preEnd,inStart){// If the start subscript is larger than the end subscript, interval processing is complete. Return null if(preStart>preEnd) return null; Const root = new TreeNode(preorder[preStart]), ind = inorder.indexof (root.val), ind = inorder.indexof (root.val) LeftSize = ind-instart; Root. left = build(preStart+1,preStart+leftSize,inStart); root.right = build(preStart+leftSize+1,preEnd,ind+1); return root; Return build(0,preorder.length-1,0)};Copy the code

At this point we are done with Leetcode-105 – constructing a binary tree by traversing pre-order and middle-order sequences

If you have any questions or suggestions, please leave a comment!