All rights reserved by DianeSoHungry (Qingyun Hu).
Original URL: https://www.cnblogs.com/DianeSoHungry/p/8891148.html
Contents
- Construct a binary tree from DLR and LDR traversals.
Problem 1
Construct a binary tree from DLR and LDR traversals.
(根据先序遍历和中序遍历序列，建二叉树）
Example:
Input：
8
1 2 4 7 3 5 6 8
4 7 2 1 5 3 8 6
Output：
Head pointer of the built binary tree
Intuition
For each DLR, you know the first element correspond to the root node. By finding the first element of DLR in LDR, you can split out the subarray of DLR and LDR for left subtree, so as to the subarray of DLR and LDR for right subtree. That is, time for recursion.
Solution in CPP
#include<iostream>
#include<queue>
struct BtNode{
int val;
BtNode* left;
BtNode* right;
BtNode(int val): val(val), left(nullptr), right(nullptr){
};
};
BtNode* BuildBT(int pre[], int mid[], int len){
if (len == 0) {
return nullptr;
}
BtNode* root;
for (int i = 0; i < len; ++i) {
if ( mid[i] == pre[0]) {
root = new BtNode(mid[i]);
root->left = BuildBT(pre+1, mid, i);
root->right = BuildBT(pre+i+1, mid+i+1, len-i-1);
break;
}
}
return root;
}
void TraverseLevelwise(BtNode* bt){
std::queue<BtNode*> q;
q.push(bt);
while (!q.empty()) {
if (q.front() != nullptr) {
std::cout << (q.front()->val) << " ";
q.push(q.front()->left);
q.push(q.front()->right);
}
else {
// std::cout << "null ";
}
q.pop();
}
std::cout << std::endl;
}
int main(){
int n;
std::cin >> n;
int preorder[n];
int midorder[n];
for (int i = 0; i < n; ++i) {
std::cin >> preorder[i];
}
for (int i = 0; i < n; ++i) {
std::cin >> midorder[i];
}
BtNode* res = BuildBT(preorder, midorder, n);
TraverseLevelwise(res);
return 0;
}
After getting the binary tree, for checking, the level order of the tree is printed as below.
1 2 3 4 5 6 7 8
Reference
《剑指offer》