2011 年机考试题

1、最大公共子串

和前面求最大公共子串一样，只不过三个的话可以用三维 dp 来解决，这里就不写了

2、中序和后序输出层次遍历

#include <iostream>
#include<queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left, * right;
    TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};

TreeNode* createTree(string inOrder, string postOrder, int left1, int right1, int left2, int right2) {
    if(left1 > right1 || left2 > right2)
        return NULL;
    TreeNode* root = new TreeNode(postOrder[right2] - '0');
    int pos = 0; // 根节点位置
    for (int i = left1; i <= right1; i++) {
        if (inOrder[i] == postOrder[right2]) {
            pos = i; break;
        }
    }
    int len = pos - left1;
    root->left = createTree(inOrder, postOrder, left1, pos - 1, left2, left2 + len - 1);
    root->right = createTree(inOrder, postOrder, pos + 1, right1, left2 + len, right2 - 1);
    return root;
}

void levelTraverse(TreeNode* root) {
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        for (int i = q.size() - 1; i >= 0; i--) {
            auto top = q.front();
            q.pop();
            cout << top->val << " ";
            if (top->left) q.push(top->left);
            if (top->right) q.push(top->right);
        }
        cout << endl;
    }
}
int main() {
    string inOrder, postOrder;
    cin >> inOrder >> postOrder;
    TreeNode* root = createTree(inOrder, postOrder, 0, inOrder.size() - 1, 0, postOrder.size() - 1);
    levelTraverse(root);
    return 0;
}