Offer 07. Rebuild binary tree
This is the 10th day of my participation in the August Text Challenge.More challenges in August
Pre-concept:
Foreordering: accesses the root node, traverses the left subtree first, and traverses the right subtree first.
Middle order: Middle order traverses the left subtree, visits the root node, and middle order traverses the right subtree.
Back-order: back-order traverses the left subtree and back-order traverses the right subtree to access the root node.
Here is:
The preceding sequence is A-B-D-G-H-E-C-F
In the sequence: G – B – D – H – E – A – C – F
After the sequence: G – H – E – B – F – D – C – A
How to build a tree:
A single tree is identified by a set (pre-middle or middle-rear);
Take this test as an example:
Preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Copy the codeFind the root node (3) in the pre array, and then find the position of 3 in the middle traversal. Then (9) to the left of 3 in the middle traversal is the left subtree of the root node, and (15, 20, 7) is the right subtree of the root node.
According to the above rules, a tree can be obtained, namely:
The solution is as follows:
The reconstruction function of binary tree reconstruction is divided into three steps:
- ** first finds the current element node, ** is the first one in pre,
- Then find its left and right subtrees in the middle order traversal (shown here as the division operation of the pre-ordinal group and the middle ordinal group), so as to construct its left and right children.
- Finally, the left and right subtrees are placed separately into the refactoring function.
For example, at this point, we find the right subtree of 3 (20, 15, 7), as shown in the figure below, which is essentially the same as the figure above, except that 3 is the root node and all other operations are the same.
Preamble: the 3-20-15-7
In order: 3-15-20-7
Repeat: ** finds the current element node, ** is the first in the preceding order, and then finds its left and right subtrees in the middle order traversal to construct its left and right children. Finding that he has no left subtree, place the left child in the constructor as shown:
Preamble: 20-15-7
In the sequence: 15-20-7
Repeat: ** finds the current element node, ** is the first in the preceding order, and then finds its left and right subtrees in the middle order traversal to construct its left and right children. Put the left and right children into the refactoring function, i.e
Until it splits into leaf nodes, and there are no left and right subtrees, it can’t split any more, so it returns itself. After the leaf node returns, the left and right subtrees of its parent node are pointed to, so it returns, step by step, and finally returns the entire binary tree.
Learn the problem with two pieces of code:
It is primarily through the first piece of code to understand the ideas of the second part.
The first section of code:
The size_left_subtree variable (the number of nodes in the left subtree);
- The root node in the middle order can be found through the key value of map ——————> Hash mapping is constructed to help us quickly locate the root node
class Solution {
private Map<Integer, Integer> indexMap;
public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return null;
}
// The first node in the forward traversal is the root node
int preorder_root = preorder_left;
// Locate the root node in the middle traversal
int inorder_root = indexMap.get(preorder[preorder_root]);
// Create the root node
TreeNode root = new TreeNode(preorder[preorder_root]);
// Get the number of nodes in the left subtree
int size_left_subtree = inorder_root - inorder_left;
// Recursively construct the left subtree and connect it to the root node
// Size_left_subtree from left +1 corresponds to size_left_subtree from left to root -1
root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// Construct the right subtree recursively and connect to the root node
// Start from left +1+ number of left subtree nodes to right, which corresponds to start from root +1 to right
root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
// Construct a hash map to help us quickly locate the root node
indexMap = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n - 1.0, n - 1); }}Copy the codeThe second part code snippet:
class Solution {
public TreeNode buildTree(int [] pre,int [] in) {
TreeNode root=ConstructCore(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
public TreeNode ConstructCore(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn)
{
/ / order before beginning the subscript > order before the end the subscript | | sequence as the starting point in sequence at the end of the subscript subscript >
if(startPre>endPre||startIn>endIn)
return null;
// Find the root node in the preceding sequence by starting subscript and create
TreeNode node = new TreeNode(pre[startPre]);
// middle order traversal
for(inti=startIn; i<=endIn; i++) {// I is the subscript of the root node
if(in[i]==pre[startPre])
{
ConstructCore(preorder traversal, preorder left subtree start subindex, preorder left subtree end subindex, middle-order traversal, middle-order left subtree start subindex, middle-order left subtree end subindex)
node.left = ConstructCore(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
node.right =ConstructCore(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
break; }}returnnode; }}Copy the codeThe hardest part of the above code to understand is as follows:
for(inti=startIn; i<=endIn; i++) {// I is the subscript of the root node
if(in[i]==pre[startPre])
{
node.left = ConstructCore(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
node.right =ConstructCore(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
break; }}Copy the codeWe analyze node.left and node.right:
node.left = ConstructCore(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
ConstructCore(preordered traversal number group, preordered left subtree start subindex (remove root node), preordered left subtree end subindex, middle-ordered traversal, middle-ordered left subtree start subindex, middle-ordered left subtree end subindex)
A: startPre + I – startIn
“I” is the subscript of the current root node, and i-startin –> indicates the number of nodes in the left subtree, preceded by the left subtree
StartPre + i-startin –> indicates the terminating index of the left subtree in the preceding ordinal group
node.right =ConstructCore(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
ConstructCore(preorder traversal, preorder right subtree start subindex, preorder right subtree end subindex, middle-order traversal, middle-order right subtree start subindex, middle-order right subtree end subindex)
I-startin –> indicates the number of nodes in the left subtree,
StartPre + i-startin –> end index of the preceding left subtree
StartPre + i-startin +1 —-> Start index of the preceding right subtree
I-1 –> The starting index of the middle-order right subtree.
References:
Code to quote: reconstruction of binary tree – > www.cnblogs.com/MrSaver/p/9…
LeetCode refers to official offer solution
The end:
If you see here or just to help you, I hope you can click a concern or 👍, thank you;
There are mistakes, welcome to point out in the comments, the author will see the modification.