Leetcode the original

Their thinking

  • Preorder [0] is the value of the current child root node

  • Find the position of the value in inorder. The left of the value is the order traversal sequence in the left subtree, and the right is the order traversal sequence in the right subtree

  • After obtaining the order traversal in the left and right subtrees, the results of the order traversal and the order traversal in the subtree are only different, but the sequence length is the same, so we can preorder to obtain the order traversal sequence of the left subtree according to the length of the order traversal sequence in the left subtree, and the rest is the order traversal sequence of the right subtree

  • 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

  • Return the root node of the binary tree

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