preface

In the previous three articles, three kinds of traversal of binary tree were carried out in three ways: pre-order, middle-order and post-order. Today, on the other hand, a binary tree was reconstructed by the results of traversal of pre-order and middle-order. This is also question 105 in Leetcode.

// Build a binary tree according to the pre-order traversal and middle-order traversal of a tree. // // Note: // You can assume that there are no repeating elements in the tree. // // for example, given // // preorder = [3,9,20,15,7] // middle order inorder = [9,3,15,20,7] // // the following binary tree is returned: // // 3 // / \ / 9 20 // / \ // 15 7 // Related Topics tree depth-first search arrayCopy the code

First of all, we will analyze the characteristics of pre-order and middle-order traversal

1. In the preceding traversal, the first traversal result is the root node of the binary tree; 2. In middle-order traversal, the left traversal result of the root node is the left subtree of the binary tree, and the right traversal result of the root node is the right subtree of the binary tree.

So let’s do an example to verify that

The preceding traversal results are as follows: [3,9,20,15,7]. The first traversal element is 3, which is the root node of the binary tree. Middle-order traversal results: [9,3,15,20,7], the left of 3 [9] is the left subtree of the binary tree, and [15,20,7] is the right subtree of the binary tree.

Thus, we can find the solution to this problem:

Find the rootNode of the binary tree rootNode(eg: 3) 2. Find the position of rootNode in the middle order traversal (the following table of eg: 3 is 1) 3. Find the result interval of left subtree foreorder and middle order traversal (eg: left subtree foreorder: [9], left subtree middle order: [9]) 4. Find the result interval of right foreorder and middle order traversal (eg: left foreorder: [20,15,7], left middle order: [15,20,7]) 5. Construct binary tree and return.

The interval search has a few details

2. The middle order interval of the left subtree is [the start point of the middle order interval of the root node, the position of the middle order interval of the root node -1] 3. The right subtree is [the middle order interval of the root node + the length of the left subtree +1, 4. The order interval of the right subtree is [the position of the order interval of the root node +1, the end point of the order interval of the root node].

In this case, the code is as follows

class Solution { private Map<Integer, Integer> inorderValue2IndexMap = new HashMap(); public TreeNode buildTree(int[] preorder, int[] inorder) { int size = preorder.length; for (int i = 0; i < inorder.length; I++) {/ / the value of the sequence traversal results in and index to establish a mapping relationship, convenient for each node in the sequence. Subscript inorderValue2IndexMap put (inorder [I], I); } return buildTree (preorder, inorder to 0, the size of 1, 0, size - 1); } private TreeNode buildTree(int[] preorder, int[] inorder, int preorderStart, int preorderEnd, int inorderStart, If (preorderEnd < preorderStart) {return null; if (preorderEnd < preorderStart) {return null; Int rootValue = preOrder [preorderStart]; TreeNode rootNode = new TreeNode(rootValue); Find the left subtree interval / / 3 Build the left subtree int inorderIndex = inorderValue2IndexMap. Get (rootValue); int leftCount = inorderIndex - inorderStart; TreeNode leftNode = buildTree(preorder, inorder, preorderStart + 1, preorderStart + leftCount, inorderStart, inorderIndex - 1); rootNode.left = leftNode; TreeNode rightNode = buildTree(preOrder, inorder, preorderStart + leftCount + 1, preorderEnd, inorderIndex + 1, inorderEnd); rootNode.right = rightNode; // 5 Return rootNode; }}Copy the code