1. Construct a binary tree from preorder and inorder traversal sequences
Here the node class is
class TreeNode{
TreeNode left;
TreeNode right;
int value;
public TreeNode(int value) {
this.value = value;
}
}
Implementation code
public class Solution {
// Construct a binary tree from preorder and inorder traversal sequences
static Map<Integer,Integer> map;
public static void main(String[] args) {
//Test it casually
int[] preorder = {1,2,3,4,5,6};
int[] inorder={3,2,4,1,6,5};
TreeNode treeNode = buildTree(preorder, inorder);
System.out.println(treeNode.value);
System.out.println(treeNode.left.left.value);
System.out.println(treeNode.right.value);
}
public static TreeNode buildTree(int[] preorder,int[] inorder){
map=new HashMap<>();
for (int i = 0; i < inorder. length; i ++ ) {
//Use map to save the corresponding position of the value of the inorder sequence
map. put(inorder[i],i);
}
//Use left close and right open
return traverseNode(preorder,0,preorder.length,inorder,0,inorder.length);
}
public static TreeNode traverseNode(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){
//The subscripts of preEnd and inEnd are just out of bounds. When preBegin and inBegin exceed, it means that the traversal is an empty tree
if (preBegin>=preEnd||inBegin>=inEnd){
return null;
}
//Find the position of the subscript of the array where the inorder traversal of the newly created node is located
int rootIndex = map.get(preorder[preBegin]);
TreeNode root = new TreeNode(inorder[rootIndex]);
//Save the number of nodes in the inorder left subtree to determine the number of preorder sequences, because the number of the two is equal (the whole place is very critical!!!)
int lenOfLeft = rootIndex - inBegin;
root.left=traverseNode(preorder,preBegin + 1,preBegin + lenOfLeft + 1,inorder,inBegin,rootIndex);
root.right=traverseNode(preorder,preBegin + lenOfLeft + 1,preEnd,inorder,rootIndex + 1,inEnd);
return root;
}
}
2. Construct a binary tree from inorder and postorder traversal sequences
import java.util.HashMap;
import java.util.Map;
public class Solution {
//Construct a binary tree from the inorder and postorder traversal sequences
static Map<Integer, Integer> map;
public static void main(String[] args) {
//Test it casually
int[] inorder = {3, 2, 4, 1, 6, 5};
int[] postorder = {3, 4, 2, 6, 5, 1};
TreeNode treeNode = buildTree(inorder, postorder);
System.out.println(treeNode.value);
System.out.println(treeNode.left.right.value);
System.out.println(treeNode.right.left.value);
}
/**
*
* @param inorder traverse the array in order
* @param postorder postorder traversal
* @return the root node of the whole tree
*/
public static TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder. length; i ++ ) {
map. put(inorder[i], i);
}
return traverseNode(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
/**
*
* @param inorder traverse the array in order
* @param inorderBegin The beginning of the subscript of the inorder array traversed this time, left closed and right closed
* @param inorderEnd The subscript end of the inorder array traversed this time, left closed and right closed
* @param postorder Traversing the array in postorder
* @param postorderBegin The beginning of the subscript of the postorder array traversed this time, left closed and right closed
* @param postorderEnd The subscript end of the postorder array traversed this time, left closed and right closed
* @return The root node of the unsorted tree is traversed this time
*/
public static TreeNode traverseNode(int[] inorder, int inorderBegin, int inorderEnd, int[] postorder, int postorderBegin, int postorderEnd) {
if (inorderBegin > inorderEnd || postorderBegin > postorderEnd) return null;
//Get the position of the in-order traversal of the node created this time
int inorderIndex = map. get(postorder[postorderEnd]);
TreeNode treeNode = new TreeNode(inorder[inorderIndex]);
int length = inorderIndex - inorderBegin;
treeNode.left = traverseNode(inorder, inorderBegin, inorderIndex - 1, postorder, postorderBegin, postorderBegin + length - 1);
treeNode.right = traverseNode(inorder, inorderIndex + 1, inorderEnd , postorder, postorderBegin + length, postorderEnd - 1);
return treeNode;
}
}
3. Generate a post-order sequence through a pre-order sequence and an in-order sequence
Corresponding sample questions PAT A1086
PTA | Auxiliary teaching platform for programming experiments
Method 1: Count the above code to generate a binary tree, and then recursively generate a postorder sequence
Explanation: This method is relatively violent. It is estimated that the time and space complexity required by PAT is not high, so this method can also be AC
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class Main{
static Map<Integer, Integer> map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer. parseInt(br. readLine());
int[] inorder = new int[n];
int[] preorder = new int[n];
int k = 0;
int preorder_i = 0;
int inorder_i = 0;
Stack<Integer> stack = new Stack<>();
while (k + + < 2 * n) {
String line = br. readLine();
if (line. charAt(1) == 'u') {
//Enter
int number = Integer. parseInt(line. split(" ")[1]);
stack. push(number);
preorder[preorder_i++] = number;
} else {
//out
inorder[inorder_i++] = stack. pop();
}
}
TreeNode1 root = buildTree(preorder, inorder);
/ / Perform post-order traversal, using recursion
traverse(root. left);
traverse(root. right);
//root node output special processing
System.out.print(root.value);
}
public static TreeNode1 buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for (int i = 0; i < inorder. length; i ++ ) {
//Use map to save the corresponding position of the value of the inorder sequence
map. put(inorder[i], i);
}
//Use left close and right open
return findNode(preorder, 0, preorder. length, inorder, 0, inorder. length);
}
public static TreeNode1 findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
//The subscripts of preEnd and inEnd are just out of bounds. When preBegin and inBegin exceed, it means that the traversal is an empty tree
if (preBegin >= preEnd || inBegin >= inEnd) {
return null;
}
//Find the position of the subscript of the array where the inorder traversal of the newly created node is located
int rootIndex = map.get(preorder[preBegin]);
TreeNode1 root = new TreeNode1(inorder[rootIndex]);
//Save the number of nodes in the inorder left subtree to determine the number of preorder sequences, because the number of the two is equal
int lenOfLeft = rootIndex - inBegin;
root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1, inorder, inBegin, rootIndex);
root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}
public static void traverse(TreeNode1 node) {
if (node == null) return;
traverse(node. left);
traverse(node.right);
System.out.print(node.value + " ");
}
}
class TreeNode1 {
TreeNode1 left;
TreeNode1 right;
int value;
public TreeNode1(int value) {
this.value = value;
}
}
Method 2: Directly generate postorder sequence without building binary tree
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
public class Main {
// There are pre-order and in-order and post-order
static ArrayList<Integer> pre, in, post, value;
public static void main(String[] args) throws IOException {
//Subscripts are stored in the front, middle and back series, and the real value needs to be subscripted by value
// Preorder traversal of the array
pre = new ArrayList<>();
//Inorder traversal of the array
in = new ArrayList<>();
// Traverse the array in postorder
post = new ArrayList<>();
//Save the value actually received, in case there is the same value
value = new ArrayList<>();
Stack<Integer> s = new Stack<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer. parseInt(br. readLine());
int k = 0;
int key = 0;
while (k + + < 2 * n) {
String line = br. readLine();
if (line. charAt(1) == 'u') {
//Enter
int number = Integer. parseInt(line. split(" ")[1]);
value. add(number);
pre.add(key);
s.push(key + + );
} else {
//out
in. add(s. pop());
}
}
postorder(0, 0, n - 1);
System.out.print(value.get(post.get(0)));
for (int i = 1; i < n; i ++ ) {
System.out.print(" " + value.get(post.get(i)));
}
}
/**
*
* @param root The starting position of the preorder traversal of this traversal
* @param start The starting position of inorder traversal this time
* @param end The end position of inorder traversal this time
*/
public static void postorder(int root, int start, int end) {
if (start > end) return;
int i = start;
for (; i < end; i ++ ) {
if (in. get(i). equals(pre. get(root))) {
break;
}
}
postorder(root + 1, start, i - 1);
// interpret root + 1 + i - 1 - start + 1
//The beginning of the first half is root + 1, and the length is ((i-1)-start) + 1
//So the second half starts as root + 1 + (((i-1)-start) + 1)=root + i-start + 1
postorder(root + 1 + i - 1 - start + 1, i + 1, end);
//The node is added at the end to meet the requirements of post-order traversal recursion
post.add(pre.get(root));
}
}
4. Generate preorder sequence through postorder sequence and inorder sequence
import java.util.ArrayList;
public class Main{
//Corresponding exercises
//There are post-order and in-order to get pre-order
//Assume there are no identical values here
static ArrayList<Integer> pre, in, post;
public static void main(String[] args) {
//Subscripts are stored in the front, middle and back series, and the real value needs to be subscripted by value
// Preorder traversal of the array
pre = new ArrayList<>();
//Inorder traversal of the array
in = new ArrayList<>();
// Traverse the array in postorder
post = new ArrayList<>();
//Take the example of the PAT 1086 tree to test
in. add(3);
in. add(2);
in. add(4);
in. add(1);
in. add(6);
in. add(5);
post. add(3);
post. add(4);
post. add(2);
post. add(6);
post. add(5);
post. add(1);
preorder(post.size()-1,0,in.size()-1);
pre.forEach(System.out::println);
}
//The root node should be the last node of the post
public static void preorder(int root, int start, int end) {
// There is a node that also needs to be sorted
if (start>end) return;
int i=start;
//In the following loop, i<=end should be changed to i<end.
//If i<end, the value is found, and it enters the loop directly. After break breaks the loop, i will not increase again, obviously there is no problem
//If i<end does not find a value (then the value must be at i=end), then i=end-1 is the last cycle, but i is still for + 1, so that i<end
//If it is not established, then the following program i is end, which happens to be the subscript of the value you are looking for
for (; i <= end; i ++ ) {
if (post.get(root).equals(in.get(i))){
//If you don't write break, i will increase to end + 1, then the following program will go out of bounds
break;
}
}
pre.add(post.get(root));
preorder((root-1)-(end-(i+1)+1),start,i-1);
preorder(root-1,i+1,end);
}
}