“This is the 25th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”
preface
In question 106 of Li Button, the binary tree is constructed from middle-order and back-order traversal sequences as follows:
The binary tree is constructed according to the middle-order traversal and post-order traversal of a tree.
Note: You can assume that there are no duplicated elements in the tree.
For example, given
Order = [9,3,15,20,7] postorder = [9,15,7,20,3]Copy the code
Return the following binary tree:
3
/ \
9 20
/ \
15 7
Copy the code
A, thinking
Restore the binary tree using middle-order and post-order traversal. If you want to build a binary tree by traversing a sequence of preorder and middle order, you can find a binary tree by traversing a sequence of preorder and middle order
We know that middle-order traversal and post-order traversal have the following characteristics:
- Middle order traversal: first
Left subtree node
Again,The root node
And, finally,Right subtree node
- Backorder traversal: first
Left subtree node
Again,Right subtree node
And, finally,The root node
If I ask you what is the root of a binary tree? You know what?
Obviously, the root of the binary tree is the last element in the sequence. What is the root of the subtree? This depends on the starting position of the current subtree and the number of nodes. Continue to look at the graphic analysis below.
Graphic algorithm
Inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
- Identify the first root node
root1
, is obviously the last node of the post-traversal
- Then find the position of the root node in the middle order traversal to determine the left subtree
left1
And right subtreeright1
. As shown below:
-
Let’s confirm the root node of the left subtree left1
Because the root node root1 is at position 2 in the middle-order traversal, the right subtree has three nodes. So the root of left1 is root1 moved forward by 4 Spaces (to remove itself)
- Reconfirm the right subtree
right1
The root node of theroot1
Before moving1
Lattice. (Since subsequent traversals are left and right roots, the root node is preceded by the last node of the right subtree, which is the root node of the right subtree.)
- Now that we’ve found all the root nodes, it’s easy to restore the binary tree. The final result is shown below:
Second, the implementation
The implementation code
The implementation code is consistent with the idea. In order to avoid repeatedly looking for the target value in the middle order traversal, Map is used to store all the node values and positions in the middle order traversal.
private Map<Integer, Integer> inMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
int n = inorder.length;
int m = postorder.length;
// Construct a hash map, remembering the position of each node in the sequence traversal
inMap = new HashMap<>();
for (int i=0; i<n; i++) {
inMap.put(inorder[i], i);
}
return dfs(postorder, 0, n-1, m-1);
}
/ * * *@paramPostorder post-order traversal *@paramIn inLeft, order traverses the start bit * of the left subtree@paramInRight in order to traverse the start bit * of the right subtree@paramPostRoot Position of the root node in subsequent traversals *@return* /
public TreeNode dfs(int[] postorder, int inLeft, int inRight, int postRoot) {
if (inLeft > inRight)
return null;
// All nodes are root nodes from back to front
TreeNode root = new TreeNode(postorder[postRoot]);
int inorder_root = inMap.get(postorder[postRoot]);
root.left = dfs(postorder, inLeft, inorder_root-1, postRoot-(inRight-inorder_root)-1);
root.right = dfs(postorder, inorder_root+1, inRight, postRoot-1);
return root;
}
Copy the code
The test code
public static void main(String[] args) {
int[] inorder = {9.3.15.20.7};
int[] postorder = {9.15.7.20.3};
TreeNode treeNode = new Number106().buildTree(inorder, postorder);
System.out.println("test");
}
Copy the code
The results of
Third, summary
Thank you to see the end, very honored to help you ~♥
If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section