One, foreword

Hello everyone, this is the fifth article in a series called “Offer of the Day”.

In this series of articles, I will review the data structure and algorithm basis by brushing questions for practice, and I will also share my brushing process in the form of blog. If you happen to want to brush up on algorithms, encourage each other to learn. My algorithm foundation is weak, and I hope to make up for this loophole in the next two or three months. The language used for this brush is Java, and it is expected that Python will be used for the second brush.

  • Leetcode’s key Offer topic
  • Code cloud warehouse address

Second, the subject

Enter the results of pre-order traversal and middle-order traversal of a binary tree, build the binary tree and return its root node.

It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers.

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

Third, the problem solving

3.1 Idea 1: Recursion

Knowledge:

  • Sequential traversal list: the first element is always root
  • In the middle of the list, all elements of root are on the left branch of the root node, and all elements on the right branch of the root node.

Algorithm idea:

  • 1. Determine [root node] through the sequential traversal list
  • 2. Split the nodes of middle-order traversal list into left branch node and right branch node.
  • 3. Recursively search for the root node in the left branch node and the root node of the right branch node.
3.1.1 code
Public static TreeNode buildTree(int[] preOrder,int[] inorder){// If (preorder.length==0){return null; } /** * 2, what should we return next? Int rootValue= preOrder [0]; rootValue=preorder[0]; int rootIndex =0; for (int i = 0; i < inorder.length; i++) { if(inorder[i]==rootValue){ rootIndex=i; TreeNode root = new TreeNode(rootValue); TreeNode root = new TreeNode(rootValue); root.left=buildTree(Arrays.copyOfRange(preorder,1,rootIndex+1),Arrays.copyOfRange(inorder,0,rootIndex)); root.right=buildTree(Arrays.copyOfRange(preorder,rootIndex+1,preorder.length),Arrays.copyOfRange(inorder,rootIndex+1,ino rder.length)); return root; }Copy the code
3.1.2 Execution Effect

3.2 Idea 2: Recursion 2

The above method is particularly inefficient because of the frequent copying of the array. Therefore, this method can change the array, and obtain the middle number from the map.

  • 1, create root node node: preorder[root]
  • 2, divide the left and right subtrees: find the root node in the middle order traversal index I inorder (use map key value pairs to find)
  • 3. Build the left subtree
3.2.1 code
class Solution { HashMap<Integer, Integer> map = new HashMap<>(); Int [] preorder; Public TreeNode buildTree(int[] preOrder, int[] inorder) {this.preorder = preorder; For (int I = 0; int I = 0; int I = 0; i < inorder.length; i++) { map.put(inorder[i], i); Return recur(0,0,inorder.length-1); return recur(0,0,inorder.length-1); } TreeNode recur(int pre_root, int in_left, int in_right){ if(in_left > in_right) return null; TreeNode root = new TreeNode(preorder[pre_root]); Int idx = map.get(preorder[pre_root]); // Get the index of the root node in the middle order traversal, Recur (pre_root+1) recur(pre_root+1) recur(pre_root+1) recur(pre_root+1) recur(pre_root+1) recur(pre_root+1) recur(pre_root+1) recur(pre_root+1) recur(pre_root+1) in_left, idx-1); // The index of the root of the right subtree is the current root position in the preceding order + the number of left subtrees +1 // The left boundary of the right subtree is the current root node in the middle order +1 // The bounded boundary of the right subtree is the original right subtree in the middle order root.right = recur(pre_root + (idx -) in_left) + 1, idx+1, in_right); return root; }}Copy the code
3.2.2 Execution Effect

3.2.3 Complexity analysis

Traversing a HashMap takes O (n) and searching takes O (1), so the time complexity is O (1).

Space complexity: Full binary tree at best, O (logN) extra space, O (N) at worst

Four,

Ontology is the first tree, examined the preorder traversal of binary tree and sequence traversal in understanding, at the same time will before choice after the first order in order to find the topic of order sequences transformed into code, subject belongs to medium difficulty, in the face of such a complex problem, need to have the ability to resolve the problem, subject of the two kinds of solution has to be done using recursion.

This is the end of today’s brush questions, welcome to like comments exchange, sword finger Offer brush questions journey will continue to unfold!