This is the 23rd day of my participation in the First Challenge 2022

Given two integer arrays preorder and inorder, where preorder is a preorder traversal of a binary tree and inorder is a middle-order traversal of the same tree, construct a binary tree and return its root node.

Input: preorder =,9,20,15,7 [3], inorder =,3,15,20,7 [9] output: [3,9,20, null, null, 15, 7]

The original link

I can only say, misguided, originally wanted to find a simple problem to do, looking at the preamble and middle preamble, but also want to be very familiar with the appearance

In fact, this problem, test is a thinking, when you understand, instantly feel not difficult, I read the solution, I also thought for a long time, this is what is going on.

So to figure out what we’re going to do here, we have to first know, what are our three traversal orders

  • Preorder: root → left → right
  • Middle order: left → root → right
  • After order: left → right → root

So we’re going to use the first two, so we need to figure out, what is the order of our two traversals, and when we look at it, we can see that one of the things that we have in common with both traversals is that we end up at the right node, and we end up at the left node and the root node in exactly the opposite order, right

By pre-order traversal we can identify our root node, and by our middle-order traversal we can find its left and right child nodes

One thing to note is that we can only identify our root node by preordering, and when we iterate through the root, we can only identify the number in front of the root node as his left node, and the number behind the root node is not necessarily his right node

Once we understand this, we can start writing our code

Public TreeNode buildTree(int[] preOrder, int[] inorder) {public TreeNode buildTree(int[] preOrder, int[] inorder) { Map<Integer,Integer> Map = new HashMap<Integer, Integer>(); for (int i = 0; i < inorder.length; Map.put (inorder[I], I); } return buildTree(preorder,map,0, preorder.length-1,0,inorder.length-1); } / / sequence traversal directly through the map in our way to our method / / pLeft, pRight, iLeft, iLeft, for our two traverse around the border / / because we have two kinds of traversal is the location of the root node and the left different public TreeNode buildTree(int[] preorder,Map<Integer,Integer> map,int pLeft,int pRight,int iLeft, int iLeft,t){ if(pLeft>pRight){ return null; } // This is the position of our root node before we iterate int pRoot = pLeft; Int iRoot = map.get(preorder[pLeft]); iRoot = map.get(preorder[pLeft]); TreeNode root = new TreeNode(preorder[pRoot]); Int leftSize = iroot-ileft; int leftSize = iroot-ileft; //pLeft+1: since the first node is our root node, shift it to the right (to make sure the new preorder traverses the left boundary) //pLeft+leftSize: The left edge plus the number of nodes in the left subtree (to determine the new right edge of the preorder traversal) Root. left = buildTree(preorder,map,pLeft+1,*pLeft+l*eftSize,iLeft,iRoot-1); Root. right = buildTree(preorder, map, pLeft+leftSize+1,pRight, iRoot+1, iRight); root.right = buildTree(preorder, map, pLeft+leftSize+1,pRight, iRoot+1, iRight); return root;Copy the code

In fact, the whole process of the code is that we constantly determine the root node to the left subtree, and when the left is done, it is the right subtree of the tree, and ends up