AcWing 1389. 美国传统
原题链接
简单
作者:
王小强
,
2021-02-09 16:55:29
,
所有人可见
,
阅读 305
二叉树的基本功
#include <iostream>
#include <algorithm>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
char val;
TreeNode *left, *right;
TreeNode(char _val) : val(_val), left(nullptr), right(nullptr) {};
~TreeNode() {
// 可以后面实现,但在面试时候,如果你写了表明至少你已经意识到了(be aware of)有内存泄漏的问题!
}
};
TreeNode* buildTree(const string& preorder, const string& inorder) {
function<TreeNode*(int, int, int)> construct = [&](int i, int j, int n) {
if (n <= 0) return (TreeNode*) nullptr;
if (n == 1) return new TreeNode(preorder[i]);
int k = j;
while (inorder[k] != preorder[i]) ++k;
const int l = k - j; // l == 左子树的长度 ...
auto root = new TreeNode(inorder[k]);
root->left = construct(i + 1, j, l);
root->right = construct(i + 1 + l, k + 1, n - l - 1);
return root;
};
return construct(0, 0, preorder.size());
}
void postOrder(TreeNode* root) {
if (!root) return;
postOrder(root->left);
postOrder(root->right);
printf("%c", root->val);
}
string inorder, preorder;
int main(void) {
cin >> inorder >> preorder;
auto root = buildTree(preorder, inorder);
postOrder(root);
return 0;
}