Directory
Purpose
foreword
Construct a binary tree from preorder and inorder traversal sequences
Construct binary tree from inorder and postorder traversal sequences
purpose
Build a binary tree based on (pre-order traversal sequence + in-order traversal sequence) or (in-order traversal sequence + post-order traversal sequence).
Preface
The order of the preorder traversal of a binary tree is:
First traverse the root node;
Then recursively traverse the left subtree;
Finally, the right subtree is traversed recursively.
The sequence for inorder traversal of a binary tree is:
Traverse the left subtree recursively first;
Then traverse the root node;
Finally, the right subtree is traversed recursively.
The order of post-order traversal of a binary tree is:
Traverse the left subtree recursively first;
Then recursively traverse the right subtree;
Finally traverse the root node.
// Preorder traversal
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
ans.push_back(root->val);
inorder(root->left);
inorder(root->right);
}
// inorder traversal
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
inorder(root->left);
ans.push_back(root->val);
inorder(root->right);
}
// Post-order traversal
void postorder(TreeNode* root) {
if (root == nullptr) {
return;
}
postorder(root->left);
postorder(root->right);
ans.push_back(root->val);
}
In the process of “recursively” traversing a subtree, we also regard this subtree as a brand new tree and traverse it in the above order. By mining the properties of “pre-order traversal”, “in-order traversal”, and “post-order traversal”, we can build a binary tree.
Construct a binary tree from preorder and inorder traversal sequences
Given two integer arrays preorder and inorder , where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct a binary tree and return its root node.
Thinking:
For any tree, the form of preorder traversal is always
[root node, [preorder traversal result of left subtree], [preorder traversal result of right subtree]]
That is, the root node is always the first node in the preorder traversal. And inorder traversal is always of the form
[ [Inorder traversal result of left subtree], root node, [Inorder traversal result of right subtree] ]
As long as we locate the root node in the in-order traversal, then we can know the number of nodes in the left subtree and the right subtree respectively. Since the lengths of pre-order traversal and in-order traversal of the same subtree are obviously the same, we can locate all left and right parentheses in the above form corresponding to the results of pre-order traversal.
In this way, we know the pre-order traversal and in-order traversal results of the left subtree, and the pre-order traversal and in-order traversal results of the right subtree, we can recursively construct the left subtree and the right subtree, Then connect the two subtrees to the left and right of the root node.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode* ConstructCore(vector<int> & amp; preorder, vector<int> & amp; inorder,int prestart,int preend,int inorderstart,int inorderend){
if(prestart > preend || inorderstart > inorderend){
return nullptr;
}
// The first node in the preorder traversal is the root node
TreeNode* root = new TreeNode;
root->left = root->right = nullptr;
root->val = preorder[prestart];
if(prestart == preend & amp; & amp; inorderstart == inorderend){
return root;
}
// locate root node in inorder traversal
int i = 0,k;
for(k = inorderstart; k <= inorderend; k++){
if(inorder[k] == preorder[prestart]){
break;
}
i + + ;
}
// Recursively construct the left subtree and connect to the root node
if(i > 0){
root->left = ConstructCore(preorder,inorder,prestart + 1,prestart + i,inorderstart,inorderstart + i -1);
}
// Recursively construct the right subtree and connect to the root node
if(inorderend - inorderstart + 1 - i > 0){
root->right = ConstructCore(preorder,inorder,prestart + i + 1,preend,inorderstart + i + 1,inorderend);
}
return root;
}
TreeNode* buildTree(vector<int> & amp; preorder, vector<int> & amp; inorder) {
int len = preorder. size();
if(len == 0){
return nullptr;
}
return ConstructCore(preorder,inorder,0,len-1,0,len-1);
}
// print binary tree
void printfTree(TreeNode* root) {
if (root == nullptr) {
cout << "null" << endl;
return;
}
queue<TreeNode*> q;
q. push(root);
while (!q.empty()) {
int size = q. size();
for (int i = 0; i < size; i ++ ) {
TreeNode* node = q. front();
q. pop();
if (node != nullptr) {
cout << node->val << " ";
q.push(node->left);
q.push(node->right);
}
else {
cout << "null ";
}
}
cout << endl;
}
}
int main(){
vector<int> preorder = {3,9,20,15,7};
vector<int> inorder = {9,3,15,20,7};
printfTree(buildTree(preorder, inorder));
return 0;
}
Run the screenshot:
Construct a binary tree from inorder and postorder traversal sequences
Given two integer arrays inorder and postorder, where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, please construct and return this binary tree.
Ideas:
Similar to the idea of preorder + inorder, we can find that the last element of the array traversed in postorder represents the root node. After knowing this property, we can use the known root node information to find the subscript of the root node in the in-order traversal array, and then divide the in-order traversal array into left and right parts according to it. The left part is the left subtree. The right part is the right subtree, and the same method can be used to continue to recursively construct each part.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode* ConstructCore(vector<int> & amp; postorder, vector<int> & amp; inorder, int p1, int p2, int in1, int in2){
if(p1 > p2 || in1 > in2){
return nullptr;
}
// The last node in the post-order traversal is the root node
TreeNode* root = new TreeNode;
root->left = root->right = nullptr;
root->val = postorder[p2];
// locate root node in inorder traversal
int i = 0 , k;
for(k = in1; k <= in2; k++){
if(inorder[k] == root->val){
break;
}
i + + ;
}
//return leaf node
if(p1 == p2 & amp; & amp; in1 == in2){
return root;
}
// Recursively construct the left/right subtree and connect to the root node
root->left = ConstructCore(postorder,inorder,p1,p1 + i-1,in1,in1 + i-1);
root->right = ConstructCore(postorder,inorder,p1 + i,p2-1,in1 + i + 1,in2);
return root;
}
TreeNode* buildTree(vector<int> & amp; postorder, vector<int> & amp; inorder) {
int len = postorder. size();
if(len == 0){
return nullptr;
}
return ConstructCore(postorder,inorder,0,len-1,0,len-1);
}
// print binary tree
void printfTree(TreeNode* root) {
if (root == nullptr) {
cout << "null" << endl;
return;
}
queue<TreeNode*> q;
q. push(root);
while (!q.empty()) {
int size = q. size();
for (int i = 0; i < size; i ++ ) {
TreeNode* node = q. front();
q. pop();
if (node != nullptr) {
cout << node->val << " ";
q.push(node->left);
q.push(node->right);
}
else {
cout << "null ";
}
}
cout << endl;
}
}
int main(){
vector<int> inorder = {9,3,15,20,7};
vector<int> postorder = {9,15,7,20,3};
printfTree(buildTree(postorder,inorder));
return 0;
}
Run the screenshot:
