4. Traversal and Reconstruction of Binary Tree

Introduction to Binary Tree

Basic structure:

function TreeNode(x) {
 this.val = x;
 this.left = null;
 this.right = null;
 }

Definition of traversal of binary tree’s pre-order, mid-order and post-order;

Preorder traversal: for any subtree, first access heel, then traverse its left subtree, and finally traverse its right subtree;

Mid-order traversal: for any subtree, first traverse its left subtree, then access its root, and finally traverse its right subtree;

Postorder traversal: For any subtree, first traverse its left subtree, then traverse its right subtree, and finally access the root.

Topic 1 Traversal of Binary Tree

1.1 topic description

Given a binary tree’s preorder traversal and preorder traversal, find its postorder traversal

Enter a description:

Two strings, the length n of which is less than or equal to 26.
The first behavior is traversal in order, and the second behavior is traversal in order.
The node names in the binary tree are expressed in capital letters: a, b, c …. up to 26 nodes.

Output description:

There may be multiple groups of input samples. For each group of test samples,
Output a line as the string traversed in the following order.

Examples:

Input
ABC
BAC
FDXEAG
XDEFAG

Output
BCA
XEDGAF

1.2 problem-solving ideas

Pre-order traversal: node+left subtree pre-order traversal+right subtree pre-order traversal

Midsequence traversal: left subtree midsequence traversal+heel node+right word count midsequence traversal

Postorder traversal: left subtree postorder traversal+right subtree postorder traversal+heel node

1. The head of the preamble traversal is the heel node

2. The middle-order traversal is divided with nodes, the left side is the left sub-middle-order traversal, and the right side is the right sub-tree middle-order traversal

3. according to the length of the right subtree of the left subtree obtained by the mid-order traversal, the pre-order traversal of the left subtree and the pre-order traversal of the right subtree are obtained

1.3 code

let pre;
 let vin;
 
 while((pre = readline())!  =null){
 vin = readline();
 print(getHRD(pre,vin));
 }
 
 function getHRD(pre, vin) {
 if (!  pre) {
 return '';
 }
 if (pre.length === 1) {
 return pre;
 }
 const head = pre[0];
 const splitIndex = vin.indexOf(head);
 const vinLeft = vin.substring(0, splitIndex);
 const vinRight = vin.substring(splitIndex + 1);
 const preLeft = pre.substring(1, splitIndex + 1);
 const preRight = pre.substring(splitIndex + 1);
 return getHRD(preLeft, vinLeft) + getHRD(preRight, vinRight) + head;

Topic 2 Binary Tree Reconstruction

2.1 topic description

Enter the results of the preorder traversal and the preorder traversal of a binary tree, please rebuild the binary tree. It is assumed that the results of the input preorder traversal and preorder traversal do not contain duplicate numbers.

For example, enter the preorder traversal sequence {1,2,4,7,3,5,6,8} and the preorder traversal sequence {4,7,2,1,5,3,8,6}, rebuild the binary tree and return.

2.2 Ideas for Solving Problems

The thinking is similar to topic 1.

According to the results of the preorder traversal and the preorder traversal, you can get:

The left subtree mid-order traversal and the right subtree mid-order traversal

Preorder Traversal of Left Subtree and Preorder Traversal of Right Subtree

Then recursively complete the reconstruction of the left subtree and the right subtree.

2.3 code

function reConstructBinaryTree(pre, vin) {
 if(pre.length === 0){
 return null;
 }
 if(pre.length === 1){
 return new TreeNode(pre[0]);
 }
 const value = pre[0];
 const index = vin.indexOf(value);
 const vinLeft = vin.slice(0,index);
 const vinRight = vin.slice(index+1);
 const preLeft = pre.slice(1,index+1);
 const preRight = pre.slice(index+1);
 const node = new TreeNode(value);
 node.left = reConstructBinaryTree(preLeft, vinLeft);
 node.right = reConstructBinaryTree(preRight, vinRight);
 return node;
 }