Topic describes

[topic address]

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

Here’s the idea:

  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

As shown in figure:

 

Code implementation

* @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */ Root left and right, middle order traversal: Left root right // According to the special constraint of traversal, the first element of the preceding traversal number group is the root node of the whole tree, we get the value of the root node // In the final traversal number group, we find the root node location mid, we can divide the left and right subtrees -- left subtrees 0~mid-1, --mid+1~inorder.length-1 var buildTree = function(preorder, inorder) {let map = new map (); for(let i = 0; i < inorder.length; i++){ map.set(inorder[i],i) } const helper = function(pStart, pEnd, iStart, IEnd){if(pStart > pEnd) return null; Let rootVal = preorder[pStart]; Let root = new TreeNode(rootVal); Let mid = map.get(rootVal); let mid = map.get(rootVal); Let leftNum = mid-istart; let leftNum = mid-istart; Root. left = helper(pStart + 1, pStart + leftNum, iStart, mid-1); Root. right = helper(pStart + leftNum + 1, pEnd, mid + 1, iEnd); return root; } return helper(0 , preorder.length -1, 0, inorder.length -1) };Copy the code