This is the 10th day of my participation in Gwen Challenge

Before we know the traversal of binary tree, in the interview, the interview questions often come out “give the pre-order restore binary tree in order or give the middle-order restore binary tree after order”. So what do we do if we encounter one?

Restore the binary tree according to the order in the preceding order

For example, if a binary tree is traversed by ACFGBDE and FCGADBE, please restore the binary tree. We do this problem, first of all to restore the binary tree, restore the binary tree according to its preorder and middle order characteristics. First of all, the first node of the pre-order traversal is the root node, from which we can get the information that A is the root node. And then we look at the order traversal, where the left of the root node is the left subtree, and the right is the right subtree. Then we know that the left subtree is FCG and the right subtree is DBE. Then we look at the preceding traversal to find the root node of the left and right subtrees. We can get that the root node of the left subtree is C, and the root node of the right subtree is B. Finally, look at the sequential traversal, the left leaf node of the left subtree is F, and the right leaf node is G. The left leaf of the right subtree is D, and the right leaf is E. We can restore the binary tree.

Code to achieve the sequential restoration of the binary tree

var qian = ['a'.'c'.'f'.'g'.'b'.'d'.'e'];
var zhong = ['f'.'c'.'g'.'a'.'d'.'b'.'e'];

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

function f1(qian,zhong) {
   if (qian == null || zhong == null || qian.length == 0 || zhong.length == 0) return null;
   var root =new Node(qian[0]);// The first of the preceding traversals is the root node
   var index = zhong.indexOf(root.value);// Find the root node in the middle order traversal position
   var qianLeft = qian.slice(1.1 + index);// The left subtree of the preceding traversal
   var qianRight = qian.slice(1 + index,qian.length);// The right subtree of the preceding traversal
   var zhongLeft = zhong.slice(0,index);// The left subtree of the sequence traversal
   var zhongRight = zhong.slice(1 + index,zhong.length);// The right subtree of the order traversal
   root.left = f1(qianLeft,zhongLeft);// Restore the left subtree from the preceding and middle order of the left subtree and assign it to root.left
   root.right = f1(qianRight,zhongRight);// Restore the right subtree is based on the preceding and middle order of the right subtree and assign it to root.right
   return root;
}
var root = f1(qian,zhong);
console.log(root.left);
console.log(root.right);
console.log(root);
Copy the code

In this way, we use the code to restore the binary tree according to the order in the preceding order.

Restore the binary tree according to the middle order after order

For example, if the middle traversal of a binary tree is FCGADBE and the rear traversal is FGCDEBA, please restore the binary tree. We do this problem, first of all to restore the binary tree, restore the binary tree according to its post-order and middle-order characteristics. First of all, the last node of the back-order traversal is the root node, from which we can get the information that A is the root node. And then we look at the order traversal, where the left of the root node is the left subtree, and the right is the right subtree. Then we know that the left subtree is FCG, and the right subtree is DBE. Then we look at the backward traversal to find the root node of the left and right subtrees. We can get that the root node of the left subtree is C, and the root node of the right subtree is B. Finally, look at the sequential traversal, the left leaf node of the left subtree is F, and the right leaf node is G. The left leaf of the right subtree is D, and the right leaf is E. We can restore the binary tree.

Code after the sequential restoration of the binary tree

var hou = ['f'.'g'.'c'.'d'.'e'.'b'.'a'];
var zhong = ['f'.'c'.'g'.'a'.'d'.'b'.'e'];

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

function f1(hou,zhong) {
   if (hou == null || zhong == null || hou.length == 0 || zhong.length == 0) return null;
   var root =new Node(hou[hou.length - 1]);// The last bit of the sequence traversal is the root node
   var index = zhong.indexOf(root.value);// Find the root node in the middle order traversal position
   var houLeft = hou.slice(0,index);// The left subtree of the post-traversal
   var houRight = hou.slice(index,hou.length - 1);// The right subtree after the sequence traversal
   var zhongLeft = zhong.slice(0,index);// The left subtree of the sequence traversal
   var zhongRight = zhong.slice(1 + index,zhong.length);// The right subtree of the order traversal
   root.left = f1(houLeft,zhongLeft);// Restore the left subtree from the last and middle order of the left subtree and assign it to root.left
   root.right = f1(houRight,zhongRight);// Restore the right subtree is based on the rear and middle order of the right subtree and assign it to root.right
   return root;
}
var root = f1(hou,zhong);
console.log(root);
console.log(root.left);
console.log(root.right);
Copy the code

In this way, we use the code to restore the binary tree according to the order in order.