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; }