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》

用C/C++码经典算法--树

Contents

Problem 1

Intuition

Solution in CPP

Reference